Python longue multiplication

Je suis dans le besoin d'un algorithme plus rapide que le courant normal Python longue multiplication.

J'ai essayé de trouver un travail décent Karatsuba mise en œuvre, mais je ne peux pas.

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

Comme vous le voyez, rien de bien compliqué, juste un peu de multiplications. Mais il a à traiter des nombres jusqu'à 100000 chiffres en moins de 2,5 secondes.

J'aimerais avoir quelques extrait d'une fonction ou juste un lien pour certains la mise en œuvre d'une multiplication plus rapide de la fonction, ou tout ce qui vous aide.

Je pense que Python utilise déjà karatsuba sous le capot (lorsqu'il est déclenché par un grand nombre de chiffres)...
Python n'utilisez déjà karatsuba pour longue multiplication. L'impression prend plus de temps que la multiplication
Est-il ok pour print(hex(a))? Il sera beaucoup plus rapide que print(a)
Avez-vous profilé de votre application? Êtes-vous sûr que la multiplication est goulot d'étranglement?
Oui , je suis sûr que la multiplication est le goulot d'étranglement parce que je dois l'imprimer en décimal , la seule chose qui reste est l'amélioration de la multiplication de la vitesse.

OriginalL'auteur Nedim | 2009-12-02