La page wikipedia sur les algorithmes de multiplication en mentionne une intéressante par Donald Knuth . Fondamentalement, cela implique de combiner la multiplication par transformée de Fourier avec une table précalculée de multiplications de taille logarithmique. Il fonctionne en temps linéaire.
L'article agit comme cet algorithme ne compte pas comme un "vrai" algorithme de multiplication. Plus important encore, il est considéré comme une question ouverte de savoir si la multiplication peut être effectuée en O(n lg n)temps égal !
Quels détails de cet algorithme l'empêchent de compter comme un "vrai" algorithme de multiplication?
Mes suppositions sont:
- Le précalcul de la table prend plus que du temps linéaire. D'un autre côté, cela peut encore être fait à
n lg ntemps, ce qui semble encore impressionnant. - L'accès aléatoire n'est en quelque sorte pas autorisé. Mais alors pourquoi d'autres algorithmes peuvent-ils utiliser des choses comme des tables de hachage et des pointeurs?
- Il évolue en quelque sorte mal lorsque vous augmentez la taille des mots d'une machine, comme si vous avez une machine 256 bits qui fait des multiplications de 256 bits dans une seule instruction, alors cet algorithme ne sert à rien tant que vous n'avez pas plus de 2 ^ 256 éléments. D'un autre côté, nous nous soucions du facteur inverse-ackermann dans l'union-find.
- Le "existe-t-il un algorithme de multiplication temporelle linéaire?" la question est secrètement en termes de machine plus faible, mais cela ne fait que faire allusion.
algorithms
runtime-analysis
multiplication
Craig Gidney
la source
la source
Réponses:
Pour une discussion sur le modèle «correct» pour la multiplication pratique de grands nombres entiers, consultez l' article récent de Fürer . Sa conclusion est en faveur de l'algorithme "pratique" de Schönhage – Strassen (il y en a deux, et l'autre a une meilleure complexité en bits mais est moins performant dans la pratique; Fürer aborde cette question dans l'article).
la source