python - Python 中的唐叶乘法 : execution time

我最近学习了唐叶乘法。为了完全理解这个概念，我尝试用 Python 编写代码并将运行时间与经典乘法进行比较。虽然结果是相等的，但 karatsuba 的执行时间仍然是最低的，尽管我使用了递归调用。我的方法有什么问题？一些帮助肯定会让我对算法设计有更多的了解。

最好的

J.P

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)

最佳答案

Karatsuba 乘法比经典二进制乘法有更大的开销

复杂性更好，但开销导致 karatsuba 对于更大的数字更快。 Karatsuba 编码的阈值操作数大小越小越好。

我在你的代码中看到你将数字转换为字符串以获得数字计数

那是 非常慢的 操作，特别是对于大数字，使用对数(恒定二进制与十进制数字之比)和二进制位计数代替。查看 here 以了解如何更快地编写 Karatsuba 代码(代码在 C++ 中)

pow 的用法

另一个减速使用 10 的幂表而不是

你把它和什么比较？ (最初由 Padraic Cunningham 问)

Karatsuba 更快，因为它对较低位计数的变量进行运算!!!我根本不在 Phyton 中编码，所以我可能会遗漏一些东西(比如任意 int)，但我没有看到任何地方你通过降低比特数 来降低数据类型，所以你总是会变慢!!! 。同样不错的是添加缓慢乘法的示例，您将时间与二进制或基数乘法进行比较......(添加您使用的内容)。如果您只使用 * 运算符，那么如果您使用的是某个 bigint lib，那么您可能正在比较 Karatsuba 与 Karatsuba 甚至 Schönhage-Strassen

时间测量

你如何衡量时间？如果不循环计算 N 时间并测量整个过程以避免精度问题，则时间应该大于 10 毫秒。还要记住 OS 的调度粒度，看看 here 如果你不知道我在写什么关于

关于python - Python 中的唐叶乘法 : execution time，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24738714/