Quel est l'algorithme le plus rapide pour la multiplication de deux nombres à n chiffres?

Je veux savoir quel algorithme est le plus rapide pour la multiplication de deux nombres à n chiffres? La complexité de l'espace peut être détendue ici!

L'algorithme de Fürer de Martin Fürer a désormais une complexité temporelle de qui utilise des transformées de Fourier sur des nombres complexes. Son algorithme est en fait basé sur l'algorithme de Schönhage et Strassen qui a une complexité temporelle de Θ ( n log ( n ) log ( log ( n ) ) $n \log(n)2^{Θ(log*(n))}$$Θ(n\log(n)\log(\log(n)))$

D'autres algorithmes qui sont plus rapides que l'algorithme de multiplication des écoles primaires sont la multiplication de Karatsuba qui a une complexité temporelle de ≈ et l'algorithme Toom 3 qui a une complexité temporelle deO ( n 1.585 ) Θ ( n 1.465$O(n^{\log_{2}3})$$O(n^{1.585})$$Θ(n^{1.465})$

Notez que ce sont les algorithmes rapides. Trouver l'algorithme le plus rapide pour la multiplication est un problème ouvert en informatique.

Les références :

1. L'algorithme de Fürer
2. Multiplication basée sur FFT de grands nombres
3. Transformée de Fourier Rapide
4. Multiplication Toom-Cook
5. Algorithme de Schönhage – Strassen
6. Algorithme de Karatsuba

Notez que les algorithmes FFT répertoriés par avi ajoutent une grande constante, ce qui les rend peu pratiques pour des nombres inférieurs à des milliers + bits.

En plus de cette liste, il existe d'autres algorithmes intéressants et des questions ouvertes:

• Multiplication temporelle linéaire sur un modèle RAM (avec précalcul)
• La multiplication par une constante est sublinéaire ( PDF ) - cela signifie un nombre sublinéaire d'additions qui obtient pour un total decomplexité en bits. Ceci est essentiellement équivalent à une longue multiplication (où vous décalez / ajoutez en fonction du nombre des dans le nombre inférieur), qui est, mais avec unaccélération à.1O(n2$\mathcal{O}\left(\frac {n^2} {\log n} \right)$$1$$\mathcal{O}\left({n^2} \right)$$\mathcal{O}\left(\log n\right)$
• Système de numération des résidus et autres représentations des nombres; la multiplication est un temps presque linéaire. L'inconvénient est que la multiplication est modulaire et {détection de débordement, parité, comparaison d'amplitude} sont toutes aussi difficiles ou presque aussi difficiles que la conversion du nombre en représentation binaire ou similaire et la comparaison traditionnelle; cette conversion est au moins aussi mauvaise que la multiplication traditionnelle (pour le moment, AFAIK).
  • Autres représentations:
    • [ Représentation logarithmique ]: la multiplication est l'addition de la représentation logarithmique. Exemple: $$16 \times 32 = 2^{\log_2 16 + \log_2 32} = 2^{4+5} = 2^{9}$$
      • L'inconvénient est que la conversion vers et depuis la représentation logarithmique peut être aussi difficile que la multiplication ou plus difficile, la représentation peut également être fractionnelle / irrationnelle / approximative, etc. D'autres opérations (addition?) Sont probablement plus difficiles.
    • Représentation canonique : représente les nombres comme les exposants de la factorisation première. La multiplication est l'addition des exposants. Exemple: $$36 \times 48 = 3^2\cdot 5^1\times 2^{2}\cdot 3^1\cdot 4^1 = {2^2}\cdot {3^2} \cdot 4^1 \cdot 5^1$$
    • L'inconvénient est, nécessite des facteurs ou factorisation, un problème beaucoup plus difficile que la multiplication. D'autres opérations telles que l'ajout sont probablement très difficiles.