我需要一种比当前正常的 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 位的数字。
我想要一些函数片段，或者只是指向更快乘法函数的某些实现的链接，或者任何有帮助的东西。
我是 DecInt（十进制整数）库的作者，所以我会发表一些评论。
DecInt 库专门设计用于处理需要转换为十进制格式的非常大的整数。转换为十进制格式的问题是大多数任意精度的库都以二进制形式存储值。这对于利用内存来说是最快和最有效的，但从二进制转换为十进制通常很慢。Python 的二进制到十进制转换使用 O(n^2) 算法，并且速度非常慢。
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)).
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.
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 很有帮助。
在我的慢速笔记本上 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 位字符串转换为 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
我建议你使用Sage 数学工具，它几乎将所有 Python 数学工具都集成到一个包中。看看 Sage 中是否有一个很好的快速任意精度数学工具可以满足您的需求。