Accélérer les multiplications d'entiers

En base 10, un nombre s'écrit sous la forme d'une somme de puissances de 10. Ainsi, 307 s'écrit 7 x 1 + 0 x 10 + 3 x 10². De la même manière, dans une base N (que l'on suppose «grande»), un entier A s'écrit

A = a + b × N + c × N² + ...

où a, b, c… sont des nombres entiers compris entre 0 et N – 1. Pour multiplier deux nombres à n chiffres, en utilisant l'algorithme classique enseigné à l'école élémentaire, on effectue n² multiplications de nombres à un chiffre, puis environ n additions (ce qui est, en pratique, «négligeable» devant les n² multiplications précédentes). En utilisant un ordinateur, le temps de calcul est ainsi proportionnel à n². Si vous doublez le nombre de chiffres, vous multipliez le temps de calcul par quatre. Bien entendu, ceci n'est «visible» que pour les nombres de plusieurs milliers de chiffres.

On peut cependant considérablement améliorer cette performance au moyen de la transformée de Fourier, dont la définition passe par le domaine complexe.

La transformation de Fourier discrète 

Un nombre A à n chiffres étant donné, on lui associe le n-uplet T(A) de nombres complexes suivant : A(1), A(ω), A(ω²)… A(ω ^n-1), où A(X) = a + bX + cX² +… et

ω = cos(2π/ n) + i sin(2π/ n) (voir ... Lire la suite gratuitement