Python 长整数乘法
我需要一个比现在普通的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位的数字。
我希望能得到一些函数的代码片段，或者链接到一些更快的乘法函数实现，或者任何有帮助的东西。
4 个回答
在我这台慢笔记本上，运行需要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
我是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有帮助。