Python中的Karatsuba乘法：執行時間

我最近學習了Karatsuba乘法。爲了充分理解這個概念，我試圖用Python編寫代碼，並將運行時間與經典乘法進行比較。儘管結果是相同的，儘管我正在使用遞歸調用，但karatsuba的執行時間仍然是最低的。我的方法有什麼問題？一些幫助肯定會讓我更多地瞭解算法設計。Python中的Karatsuba乘法：執行時間

最佳

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

有哪些你所使用的輸入和結果？你可以發佈這些？ –

你在比較什麼？ –

你的算法應該乘號，如果是< 10：

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

karatsuba1是你的原代碼。 karatsuba使用if int(len_x) < 10 or int(len_y) < 10

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

來源

2014-07-14 15:23:21

Karatsuba乘法具有更大的額外開銷那麼經典二進制乘法

複雜越好，但開銷的原因是karatsuba是更大的數字快。最好是Karatsuba編碼的閾值操作數大小越小。
我在你的代碼中看到，你轉換號碼字符串來獲得數字計數

是很慢操作尤其是對於大的數字，用對數（恆定二進制到十進制數字比）和二進制位反而計數。看here的想法怎麼樣編寫Karatsuba更快（代碼爲C++）
戰俘的使用

的10次冪的另一減緩使用表而不是
你在比較什麼？（最初由Padraic Cunningham提問）

Karatsuba更快，因爲它可以在較低的位計數變量上進行操作！我沒有在Phyton的代碼中，所以我可以忽略一些東西（比如任意int），但我沒有看到任何地方降低了數據類型，降低了比特數，所以你會一直比較慢！。還不錯，將添加慢乘法的例子，你比較時間喜歡二進制或基數乘法...（添加你使用的）。如果你，如果你是在一些BIGINT lib中只使用*然後操作員那麼很可能你是比較Karatsuba與Karatsuba甚至Schönhage-Strassen的
時間測量

怎麼辦你測量時間？如果不循環計算N次並且測量整個事情以避免準確性問題，則時間應該大於10ms。也可參加OS的頭腦調度粒度看here，如果你不知道我寫

來源

2014-07-15 07:35:07 Spektre

Python中的Karatsuba乘法：執行時間

回答

相關問題