Ich brauche einen Algorithmus, der schneller ist als die derzeitige normale Python-Long-Multiplikation.

Ich habe versucht, eine anständige Karatsuba-Implementierung zu finden, aber ich kann nicht.

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

Wie Sie sehen, ist es nicht kompliziert, nur ein paar Multiplikationen. Es muss aber Zahlen mit bis zu 100000 Ziffern in weniger als 2,5 Sekunden verarbeiten.

Ich hätte gerne einen Auszug aus einer Funktion oder nur einen Link zu einer Implementierung einer schnelleren Multiplikationsfunktion oder etwas, das hilft.