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(Decimal Integer)库的作者,所以我会发表一些评论.

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针对的是一个非常小的利基市场.对于足够大的数字,Deci将比原生Python更快地进行乘法和除法.但如果你追求纯粹的表现,像GMPY这样的图书馆将是最快的.

我很高兴您发现DecInt很有帮助.

Answer 2

在我的慢速笔记本上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