Długie mnożenie Pythona
Potrzebuję algorytmu szybszego niż obecne normalne długie mnożenie Pythona.
Próbowałem znaleźć porządną implementację Karatsuba, ale nie mogę.
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()
Jak widzisz, nie jest to nic skomplikowanego, tylko kilka powtórzeń. Musi jednak obsługiwać liczby do 100000 cyfr w czasie poniżej 2,5 sekundy.
Chciałbym jakiś fragment funkcji lub po prostu link do implementacji szybszej funkcji mnożenia lub czegoś, co pomaga.