Python长乘法

问题描述

我需要一种比当前普通的Python长乘法更快的算法.

I'm in need of an algorithm faster than the current normal Python long multiplication.

我试图找到一个不错的Karatsuba实现，但是我找不到.

I tried to find a decent Karatsuba implementation, but I can't.

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位数字.

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.

我想要一个函数的代码片段，或者一个指向快速乘法函数的实现的链接，或者任何有帮助的东西.

I'd like some snippet of a function or just a link to some implementation of a faster multiplication function, or anything that helps.

推荐答案

您可以看看 DecInt模块(纯Python版本可用(Toom-Cook)，尽管使用脾气暴躁).

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).

这篇关于Python长乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！