Python longue multiplication

Question

J'ai besoin d'un algorithme plus rapide que la multiplication longue normale de Python.

J'ai essayé de trouver une implémentation décente de Karatsuba, 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, ce n'est rien de compliqué, juste quelques multiplications. Mais il doit gérer des nombres allant jusqu'à 100 000 chiffres en moins de 2,5 secondes. Je voudrais un extrait d'une fonction ou juste un lien vers une implémentation 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 DecInt module (version pure Python est disponible (Toom-Cook), mais le plus rapide, il sera probablement en utilisant gmpy).

Answer 2

Je suggère que vous obteniez le Sage math tool, qui a à peu près tous les outils de mathématiques Python jamais faits en un seul paquet. Voyez s'il existe dans Sage un bon outil mathématique de précision rapide et arbitraire qui répond à vos besoins.

Answer 3

15,9 ms sur mon ordinateur portable lent. C'est l'impression qui vous ralentit. La conversion en nombre binaire en décimal est assez lente, ce qui est une étape nécessaire pour l'imprimer. Si vous avez besoin de sortir le numéro, vous devriez déjà essayer DecInt ChristopheD.

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 suis l'auteur de la bibliothèque DecInt (entier décimal) donc je vais faire quelques commentaires.

La bibliothèque DecInt a été spécialement conçue pour fonctionner avec de très grands entiers devant être convertis au format décimal. Le problème avec la conversion au format décimal est que la plupart des bibliothèques de précision arbitraire stockent des valeurs en binaire. C'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 lente. La conversion binaire en décimal de Python utilise un algorithme O (n^2) et ralentit très rapidement.

DecInt utilise une grande base décimale (généralement 10^250) et stocke le très grand nombre dans des blocs de 250 chiffres. La conversion d'un très grand nombre au format décimal est maintenant exécutée dans O (n). Naïf, ou école primaire, la multiplication a un temps d'exécution de O (n^2). Python utilise la multiplication de Karatsuba qui a le temps d'exécution de O (n^1.585). DecInt utilise une combinaison de convolutions de Karatsuba, de Toom-Cook et de Nussbaumer pour obtenir un temps de fonctionnement de O (n * ln (n)).

Même si DecInt a un surdébit beaucoup plus élevé, la combinaison de la multiplication O (n * ln (n)) et de la conversion O (n) sera plus rapide que la multiplication O (n^1.585) et O (n^2)) conversion.

Comme la plupart des calculs ne nécessitent pas l'affichage de tous les résultats au format décimal, presque toutes les bibliothèques de précision arbitraire utilisent des binaires car cela facilite les calculs. DecInt vise un très petit créneau. Pour des nombres assez grands, DecInt sera plus rapide pour la multiplication et la division que Python natif. Mais si vous recherchez une performance pure, une librairie comme GMPY sera la plus rapide.

Je suis content que vous ayez trouvé DecInt utile.