题

我需要一个算法的速度比目前的正常Python长乘法运算。

我试图找到一个体面的Karatsuba实现，但我不能。

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

正如你看到的，这是没有什么复杂的，只有几次乘法。但是它已经处理的数字与最100000数字低于2.5微秒。

我想要一些片段的一个函数，或只是一个链接到一些执行的乘法运算速度更快功能，或任何帮助。

有帮助吗？

解决方案

您可以看看的 DecInt模块（纯Python版本的实现可用（TOOM库克）虽然用最快时 gmpy ）它可能会。

其他提示

我是作者的DecInt(整数)图书馆，所以我只作几点评论。

该DecInt库是具体的设计工作有很大的整数需要被转换到小数点的格式。该问题转换为小格式是，大多数任意的-精确的库存值在二进制的。这是最快和最有效的利用存储器，但转换的二十进制的通常是缓慢的。蟒蛇的二十进制转换使用O(n^2)算法而得到缓慢的速度非常快。

DecInt使用大小基数(通常为10^250)和存储的数量非常大块的250的数字。转换成非常大的数十进制的格式现已运行在O(n)。

天真，或等级学校、乘有一个运行时间O(n^2).Python使用Karatsuba乘哪个有运行时间O(n^1.585).DecInt结合使用Karatsuba,Toom做的，夫努斯鲍默的卷积得到一个运行时间O(n*ln(n))。

即使DecInt具有高得多的开销，该组合的O(n*ln(n))乘法和O(n)转换将最终以更快的速度比Python O(n^1.585)乘法和O(n^2)转换。

由于大多数的计算不需要每一个的结果将显示在十进制的格式，几乎每一个任意的精库使用的二进制由于使计算较容易。DecInt目标的一个非常小的地位。足够大的数字，DecInt将以更快的速度的乘法和司比本地蟒蛇。但如果你是纯粹的性能、图书馆等GMPY将是最快的。

我很高兴你找到DecInt有帮助的。

15.9毫秒我缓慢的笔记本电脑。这是放慢你失望的打印。转换为二进制数十进制是相当缓慢的，这是打印出来的必要步骤。如果你需要输出的数量，您应该尝试DecInt ChristopheD已经提到的。

DecInt会慢做乘法，但使打印速度更快

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

下面是与您的代码的一个略加修改的版本的示例。请注意，一个100000的数字串转换为长已经发生〜此计算机上1秒

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

我建议你在贤者数学工具，这已几乎所有Python的数学工具有史以来热轧在一个封装中。看看是否有在圣人一个不错的快速任意精度的数学工具，满足您的需求。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top