longue multiplication Python

Question

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

J'ai essayé de trouver une mise en œuvre Karatsuba décent, 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, il n'y a rien compliqué, à seulement quelques multiplications. Mais il doit gérer un nombre avec un maximum de 100000 chiffres en moins de 2,5 s.

Je voudrais une extrait d'une fonction ou tout simplement un lien vers une mise en œuvre d'une fonction de multiplication plus rapide, ou tout ce qui aide.

Answer 1

Vous pouvez jeter un oeil à la mise en œuvre de la (pur Python version DecInt Module est disponible (Toom-Cook), bien que le plus rapide, il sera probablement lors de l'utilisation gmpy ).

Answer 2

Je suis l'auteur de la bibliothèque DecInt (décimal entier) donc je vais faire quelques commentaires.

La bibliothèque DecInt a été spécialement conçu pour fonctionner avec de très grands nombres entiers qui doivent être convertis au format décimal. Le problème avec la conversion au format décimal est que la plupart des valeurs des magasins de bibliothèques de précision arbitraire en binaire. Ceci est le plus rapide et le plus efficace pour utiliser la mémoire, mais la conversion de binaire en décimal est généralement lent. Le binaire Python en décimal conversion utilise un O (n ^ 2) algorithme et devient lent très rapidement.

DecInt utilise une grande radix décimale (généralement 10 ^ 250) et stocke le très grand nombre de blocs de 250 chiffres. La conversion d'un très grand nombre au format décimal fonctionne maintenant en O (n).

Naïf, ou l'école primaire, la multiplication a une durée de O (n ^ 2). Python utilise multiplication Karatsuba qui a le temps de marche de O (n ^ 1,585). DecInt utilise une combinaison de Karatsuba, Toom-Cook, et convolution Nussbaumer pour obtenir une durée de O (n * ln (n)).

Même si DecInt a beaucoup les frais généraux plus élevés, la combinaison de O (n * ln (n)) multiplication et O (n) conversion finiront par être plus rapide que O Python (n ^ 1,585) multiplication et O (n ^ 2) conversion.

Comme la plupart des calculs ne nécessitent pas tous les résultats à afficher au format décimal, presque toutes les bibliothèques de précision arbitraire utilise binaire depuis qui rend les calculs plus facile. DecInt cible un créneau très faible. Pour nombre suffisant, DecInt sera plus rapide pour la multiplication et la division que Python natif. Mais si vous êtes après la performance pure, une bibliothèque comme gmpy sera le plus rapide.

Je suis heureux que vous ayez trouvé DecInt utile.

Answer 3

15,9 ms sur mon ordinateur portable lent. Il est l'impression qui vous ralentit. Conversion en nombres binaires en décimal est assez lent, ce qui est une étape nécessaire de l'imprimer. Si vous avez besoin de sortir le numéro que vous devriez essayer le DecInt ChristopheD déjà mentionné.

DecInt sera plus lent à faire la multiplication, mais rendre l'impression beaucoup plus rapide

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

Voici un exemple avec une version légèrement modifiée de votre code. Notez que la conversion d'une chaîne de chiffres 100000 à une longue prend déjà ~ 1sec sur cet ordinateur

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

Answer 4

Je vous suggère de faire outil mathématique Sage , qui a à peu près tous les outils mathématiques de Python jamais fait laminés dans un seul paquet. Voir s'il y a un bel outil de maths de précision arbitraire rapide Sage qui répond à vos besoins.