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(十进制整数)库的作者，所以我会发表一些评论。

DecInt 库专门设计用于处理需要转换为十进制格式的非常大的整数。转换为十进制格式的问题是大多数任意精度库以二进制形式存储值。这对于利用内存来说是最快和最有效的，但是从二进制转换为十进制通常很慢。 Python 的二进制到十进制的转换使用 O(n^2) 算法并且速度很快。

DecInt 使用大十进制基数(通常为 10^250)并将非常大的数字存储在 250 位数字的 block 中。将非常大的数字转换为十进制格式现在在 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 这样的库将是最快的。

很高兴您发现 DecInt 对您有所帮助。