Python长乘法

Question

我需要一个比目前常用的Python长乘法更快的算法。

我试图找到一个像样的空手道，但我做不到

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秒内处理高达10万位的数字。

我想要一个函数的片段，或者只是一个快速乘法函数实现的链接，或者任何有用的东西。

Answer 1

15.9毫秒在我的慢笔记本上。是指纹让你慢下来。把二进制数转换成十进制数是相当慢的，这是打印出来的必经步骤。如果你需要输出数字，你应该尝试克里斯托弗已经提到的小数。

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

Answer 2

我是DecInt（Decimal Integer）库的作者，所以我要做一些评论。

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

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

幼稚的，或小学的，乘法运算的运行时间是O（n^2）。Python使用运行时间为O（n^1.585）的Karatsuba乘法。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这样的库将是最快的。

我很高兴你能帮上忙。

Answer 3

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