Python长乘法

Question

我需要一种比目前普通的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()

如您所见，这并不复杂，只需要几次乘法。但它必须在2.5秒内处理最多100000位数字。

我想要一些函数的片段，或者只是到更快的乘法函数的实现的链接，或者任何有帮助的东西。

Answer 1

您可以看看DecInt module的实现(纯Python版本可用(Toom-Cook)，尽管在使用gmpy时可能是最快的)。

Answer 2

我是DecInt (十进制整数)库的作者，所以我将做一些评论。

DecInt库专门设计用于处理需要转换为十进制格式的非常大的整数。转换为十进制格式的问题是，大多数任意精度的库都以二进制形式存储值。这对于利用内存来说是最快和最有效的，但是从二进制到十进制的转换通常很慢。Python的二进制到十进制转换使用O(n^2)算法，速度非常快。

DecInt使用大的小数基数(通常是10^250)，并将非常大的数字存储在250位的块中。将一个非常大的数字转换为十进制格式现在运行在O(n)中。

幼稚，或小学，乘法的运行时间为O(n^2)。Python使用Karatsuba乘法，其运行时间为O(n^1.585)。DecInt使用Karatsuba，Toom-Cook和Nussbaumer卷积的组合来获得O(n*ln(n))的运行时间。

尽管DecInt的开销要高得多，但O(n*ln(n))乘法和O(n)转换的组合最终将比Python的O(n^1.585)乘法和O(n^2)转换更快。

由于大多数计算并不要求每个结果都以十进制格式显示，因此几乎每个任意精度的库都使用二进制，因为这使得计算更容易。DecInt的目标是非常小的利基市场。对于足够大的数字，DecInt的乘法和除法运算速度将比原生Python快。但是如果你追求的是纯粹的性能，像GMPY这样的库将是最快的。

我很高兴你发现DecInt很有帮助。

Answer 3

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