Python에서 Karatsuba 곱셈 : 실행 시간

나는 최근에 Karatsuba 곱셈을 배웠습니다. 이 개념을 완전히 이해하기 위해 Python으로 코드를 작성하고 실행 시간을 고전적인 곱셈과 비교했습니다. 결과는 같지만 재귀 호출을 사용하고 있지만 karatsuba의 실행 시간은 여전히 가장 낮습니다. 내 접근 방식에 문제가 있습니까? 알고리즘 설계에 대해 더 많은 것을 이해할 수있는 도움을 주기도합니다.Python에서 Karatsuba 곱셈 : 실행 시간

최저

JP (가) < 10 경우

print('Karatsuba multiplication in Python') 
x=raw_input("first_number=") 
y=raw_input("second_number=") 
print('------------------------') 
x=int(x) 
y=int(y) 
import math 
import time 
def karatsuba(x,y): 

    x=str(x) 
    y=str(y) 

    len_x=len(x) 
    len_y=len(y) 

    if(int(len_x)==1 or int(len_y)==1):  
    return int(x)*int(y) 
    else: 

    B=10 
    exp1=int(math.ceil(len_x/2.0)) 
    exp2=int(math.ceil(len_y/2.0)) 
    if(exp1<exp2): 
     exp=exp1 
    else: 
     exp=exp2 
    m1=len_x-exp 
    m2=len_y-exp 
    a=karatsuba(int(x[0:m1]),int(y[0:m2])) 
    c=karatsuba(int(x[m1:len_x]),int(y[m2:len_y])) 
    b=karatsuba(int(x[0:m1])+int(x[m1:len_x]),int(y[0:m2])+int(y[m2:len_y]))-a-c 
    results=a*math.pow(10,2*exp) + b*math.pow(10,exp) + c 
    return int(results) 

start_time=time.time() 
ctrl = x*y 
tpt=time.time() - start_time 
print x,'*',y,'=',ctrl 
print("--- %s seconds ---" % tpt) 

start_time=time.time() 
output=karatsuba(x,y) 
tpt=time.time() - start_time 
print 'karatsuba(',x,',',y,')=',output 
print("--- %s seconds ---" % tpt)

출처

2014-07-14 Jean-Paul Abbuehl

사용한 입력과 결과는 무엇인가? 그것들을 게시 할 수 있습니까? –

무엇을 비교하고 있습니까? –

알고리즘 숫자를 곱해야합니다

if int(len_x) < 10 or int(len_y) < 10:

karatsuba1 원래 코드입니다. karatsuba는

In [17]: %timeit karatsuba1(999,999) 
100000 loops, best of 3: 13.3 µs per loop 

In [18]: %timeit karatsuba(999,999) 
1000000 loops, best of 3: 1.77 µs per loop

if int(len_x) < 10 or int(len_y) < 10을 사용

출처

2014-07-14 15:23:21

카라 츠바 곱셈 후 더 큰 오버 헤드 고전 이진 곱셈

복잡성이 더 있지만 카라 츠바 더 빨리 더 큰 숫자입니다 오버 헤드 원인이있다. 더 나은 것은 Karatsuba이 임계 값 피연산자 크기보다 작은 값을 코드화 한 것입니다. 당신이 자리 수 매우 느린 작업이 특히 큰 숫자가 대수 (상수 이진 자릿수 비율 십진하는)과 이진 비트를 사용을위한

을 얻기 위해 문자열로 숫자를 변환 난 당신의 코드에서 볼
대신에 계산하십시오. 코딩하는 방법에 대한 아이디어를 here를 봐 카라 츠바 빠른

펑의 사용

10의 거듭 제곱의 또 다른 천천히 아래로 사용 테이블 대신

(코드 C++에) 너는 그것을 무엇과 비교하고 있니? (원래 Padraic 커닝햄에 의해 요청)

가 낮은 비트 카운트 변수에 대한 작업을 수행하기 때문에 카라 츠바가 빠르다! 나는 코드를 작성하지 않는다 Phyton 전혀 (임의의 int와 같은) 뭔가를 놓칠 수는 있지만 비트 수를 낮추면서 데이터 유형을 낮추는 것은 어디에도 보이지 않는다. 그래서 항상 느려진다 !!!. 또한 당신은 시간을 이진 또는 기수 곱셈과 같이 비교하는 느린 곱셈의 예제를 추가하는 것이 좋습니다 ... (사용하는 것을 더하십시오).일부 BIGINT lib 디렉토리에있는 경우 당신은 그럼 그냥 * 연산자를 사용하는 경우, 당신이 카라 츠바 또는 Schönhage-쉬트 라쎈

시간 측정

가 수행하는 방법과 카라 츠바을 비교하는 것이 가능하다 너는 시간을 측정하니? 시간은 더 큰 다음 10ms 계산을 루프하지 않으면 N 번 정확성 문제를 피하기 위해 모든 것을 측정해야합니다. 당신은 내가 쓰고 무엇을 아무 생각이없는 경우 또한가 here 보일 OS의 마음 스케줄링 단위에 걸릴에 대한

출처

2014-07-15 07:35:07 Spektre

Python에서 Karatsuba 곱셈 : 실행 시간

답변

관련 문제