Python 长乘法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1835857/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python long multiplication
提问by Nedim
I'm in need of an algorithm faster than the current normal Python long multiplication.
我需要一种比当前正常的 Python 长乘法更快的算法。
I tried to find a decent Karatsuba implementation, but I can't.
我试图找到一个像样的 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()
As you see, it's nothing complicated, just a few multiplications. But it has to handle numbers with up to 100000 digits in under 2.5 sec.
如您所见，这并不复杂，只是几个乘法。但它必须在 2.5 秒内处理多达 100000 位的数字。
I'd like some snippet of a function or just a link to some implementation of a faster multiplication function, or anything that helps.
我想要一些函数的片段，或者只是一个更快的乘法函数的一些实现的链接，或者任何有帮助的东西。
采纳答案by ChristopheD
You could have a look at the implementation of the DecInt module(pure Python version is available (Toom-Cook) although the fastest it will probably be when using gmpy).
您可以查看DecInt 模块的实现（可以使用纯 Python 版本（Toom-Cook），尽管使用gmpy时速度可能最快）。
回答by casevh
I'm the author of the DecInt (Decimal Integer) library so I'll make a few comments.
我是 DecInt（十进制整数）库的作者，所以我会发表一些评论。
The DecInt library was specifically designed to work with very large integers that needed to be converted to decimal format. The problem with converting to decimal format is that most arbitrary-precision libraries store values in binary. This is fastest and most efficient for utilizing memory but converting from binary to decimal is usually slow. Python's binary to decimal conversion uses an O(n^2) algorithm and gets slow very quickly.
DecInt 库专门设计用于处理需要转换为十进制格式的非常大的整数。转换为十进制格式的问题在于，大多数任意精度的库都以二进制形式存储值。这对于利用内存来说是最快和最有效的，但从二进制转换为十进制通常很慢。Python 的二进制到十进制转换使用 O(n^2) 算法并且速度很快。
DecInt uses a large decimal radix (usually 10^250) and stores the very large number in blocks of 250 digits. Converting a very large number to decimal format now runs in O(n).
DecInt 使用大十进制基数（通常为 10^250）并将非常大的数字存储在 250 位的块中。将非常大的数字转换为十进制格式现在在 O(n) 中运行。
Naive, or grade school, multiplication has a running time of O(n^2). Python uses Karatsuba multiplication which has running time of O(n^1.585). DecInt uses a combination of Karatsuba, Toom-Cook, and Nussbaumer convolution to get a running time of O(n*ln(n)).
天真的或小学，乘法的运行时间为 O(n^2)。Python 使用 Karatsuba 乘法，其运行时间为 O(n^1.585)。DecInt 使用 Karatsuba、Toom-Cook 和 Nussbaumer 卷积的组合来获得 O(n*ln(n)) 的运行时间。
Even though DecInt has much higher overhead, the combination of O(n*ln(n)) multiplication and O(n) conversion will eventually be faster than Python's O(n^1.585) multiplication and O(n^2) conversion.
尽管 DecInt 的开销要高得多，但 O(n*ln(n)) 乘法和 O(n) 转换的组合最终将比 Python 的 O(n^1.585) 乘法和 O(n^2) 转换更快。
Since most computations don't require every result to be displayed in decimal format, almost every arbitrary-precision library uses binary since that makes the computations easier. DecInt targets a very small niche. For large enough numbers, DecInt will be faster for multiplication and division than native Python. But if you are after pure performance, a library like GMPY will be the fastest.
由于大多数计算不需要每个结果都以十进制格式显示，几乎每个任意精度的库都使用二进制，因为这使计算更容易。DecInt 的目标是一个非常小的利基市场。对于足够大的数字，DecInt 的乘法和除法比原生 Python 更快。但如果你追求纯粹的性能，像 GMPY 这样的库将是最快的。
I'm glad you found DecInt helpful.
我很高兴你发现 DecInt 有帮助。
回答by John La Rooy
15.9 ms on my slow notebook. It is the print that is slowing you down. Converting to binary numbers to decimal is quite slow, which is a required step of printing it out. If you need to output the number you should try the DecInt ChristopheD mentioned already.
在我的慢速笔记本上为 15.9 毫秒。是印刷品让你慢下来。将二进制数转换为十进制数非常慢，这是打印出来的必要步骤。如果您需要输出数字，您应该尝试已经提到的 DecInt ChristopheD。
DecInt will be slower doing the multiply but make the print much faster
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
Here is an example with a slightly modified version of your code. Note that converting a 100000 digit string to a long already takes ~1sec on this computer
这是一个示例，其中包含稍微修改过的代码版本。请注意，在此计算机上将 100000 位字符串转换为 long 已经需要大约 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
回答by steveha
I suggest you get the Sage math tool, which has just about every Python math tool ever made rolled into one package. See if there is a nice fast arbitrary precision math tool in Sage that meets your needs.
我建议您使用Sage 数学工具，它几乎将所有 Python 数学工具都整合到一个包中。看看 Sage 中是否有一个很好的快速任意精度数学工具可以满足您的需求。
