Accélérer les multiplications d'entiers
Publié le 08/07/2017
Résumé

Les nombres complexes semblent très éloignés des questions de rentabilité du monde moderne. Pourtant, ils sont à l'origine de méthodes utilisées pour accélérer les multiplications de grands nombres entiers. Ils permettent de gagner du temps, beaucoup de temps… et donc de l'argent !

Accélérer les multiplications d'entiers


Auteur : Hervé Lehning

Une collaboration de CultureMath et du Magazine Tangente ;

Cet article est extrait d'un dossier complet et passionnant sur les nombres complexes publié dans le numéro HS 63 du Magazine Tangente.

Le numéo complet et bien plus encore en suivant ce lien : Les nombres complexes


 

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 102. De la même manière, dans une base N (que l’on suppose «grande»), un entier A s’écrit

A = a + b x N + c x N2 + ...

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 n2 multiplications de nombres à un chiffre, puis environ n additions (ce qui est, en pratique, «négligeable» devant les n2 multiplications précédentes). En utilisant un ordinateur, le temps de calcul est ainsi proportionnel à n2. 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(ω2)… A(ω n-1), où A(X) = a + bX + cX2 +…   et

  ω = cos(2π/ n) + sin(2π/ n) (voir l’encadré sur les racines de l’unité à la fin de cet article).

Ce calcul demande a priori n2 multiplications, donc un temps de calcul proportionnel à n2, mais en fait une méthode subtile permet de l’effectuer dans un temps proportionnel à n ln (où ln n désigne le logarithme népérien de n), ce qui est beaucoup plus rapide ! Par exemple, cela fait passer d’un million d’opérations à sept mille, ou encore d’un milliard d’opérations à trois cent mille, ce qui est considérable. Dans la pratique (c’est-à-dire pour les ordinateurs), on préfère parler de complexité de calcul plutôt que de « temps de calcul », ce qui correspond à une modélisation pertinente de ce temps de calcul. On l’effectue en comptant le nombre d’opérations nécessaires, en se restreignant aux plus gourmandes en temps, ici les multiplications ordinaires.

L’intérêt de la transformation T, appelée transformation de Fourier discrète de A, est d’être inversible, c’est-à-dire que la connaissance de T(A) permet de reconstituer A. Le calcul consiste simplement à résoudre le système d’équations suivant :

a + b + c + … = A(1),

a + b ω + c ω2 + … = A(ω),

a + b ωn-1 + c ω2(n-1) + … = A(ωn-1),

dans lequel les inconnues sont a, b, c

Comme la somme des racines nèmes de l’unité est nulle (voir l’encadré dessous), il suffit d’ajouter toutes les équations pour obtenir a = [A(1) + A(ω) + … + A(ωn-1)] / n.

De même, on obtient b en multipliant la dernière équation par ω, l’avant-dernière par ω2, etc. : b = [A(1) + ωn-1 A(ω) + … + ω A(ωn-1)] / n, et ainsi de suite. Le passage de T(A) à A est de même nature que celui de A à T(A), la seule différence est la division finale par n. La méthode rapide permet de l’effectuer dans un temps proportionnel à n ln n.

Étant donnés deux nombres A et B, on peut calculer leurs transformées de Fourier discrètes T(A) et T(B) dans un temps proportionnel à n ln n. On les multiplie alors entre elles, pour obtenir C(1) = A(1) B(1), C(ω) = A(ω) B(ω), etc., ce qui demande n multiplications.

Il est alors facile de reconstituer C en un temps proportionnel à n ln n. On obtient donc le produit C = A B en un temps proportionnel à n ln n au lieu de n2. Voila un intérêt de la transformée de Fourier discrète, et donc des nombres complexes : gagner du temps, donc de l’argent, dans les calculs arithmétiques ! Ceux-ci sont indispensables en cryptographie, d’utilisation constante (en particulier sur Internet).

 

Toujours plus vite

Supposons que A possède 2n chiffres (ce que l’on peut toujours supposer en ajoutant un zéro en tête) : A = a + b N + c N2 + d N3 + e N4 + ... On sépare les termes d’ordre pair de ceux d’ordre impair : A0 = a + c N + e N2 + ...  et  A1 = b + d N + ... En considérant les polynômes associés, cela donne A(X) = A0(X2) + X A1(X2). Si ω = cos (2π / 2n) + i sin (2π / 2n), alors ω2 = cos(2π / n) + i sin(2π / n), donc les formules 

A(1) = A0(1) + A1(1), 

A(ω) = A02) + ω A12)

... 

A(ωn-1) = A02(n-1)) + ωn-1 A12(n-1)

montrent que, pour calculer une transformée de Fourier discrète d’un nombre à 2n chiffres, il suffit d’en calculer deux à n chiffres, puis d’effectuer n multiplications et n additions. Si l’on note c(n) le nombre de multiplications nécessaires pour calculer la transformée de Fourier discrète d’un nombre de n chiffres, c vérifie c(2n) = 2 c(n) + n. En résolvant cette relation de récurrence, on montre que c(n) est de l’ordre de grandeur de n ln n (voir le calcul en encadré). Cela implique que les calculs de la transformée doivent se faire de façon récursive, en divisant successivement le nombre de chiffres par 2. Vous êtes alors en mesure de multiplier rapidement deux nombres, et le gain de temps, considérable, dans l’exécution de vos programmes vous offre un avantage certain sur ceux qui utilisent des algorithmes naïfs.

 


Les racines de l'unité

 

D’après la formule de Moivre, si ω = cos(2ω / n) + i sin(2ω / n), alors ωk = cos(2kπ / n) + i sin(2kπ / n) donc 1, ω, ω2… ω n-1 sont n racines nèmes distinctes de l’unité. On les a ainsi toutes énumérées.

D’autre part, (1 – ω)(1 + ω + ω2 + … + ωn-1) = 1 – ωn = 0, donc la somme des racines nèmes de l’unité est nulle. De même si l’on remplace ω par ωk, où k est un entier quelconque compris entre 1 et n – 1. 

 

Un calcul de complexité

Considérons une fonction c telle que c(0) = 1 et c(2n) = 2 c(n) + n pour tout n ≥ 1.

Si l’on pose un = c(2n) / 2n, cette suite vérifie la relation de récurrence un+1 = un +1/2 et u0 = 1, d’où un = (n + 1) / 2 et donc c(2n) = 2n (n + 1) / 2. On démontre alors, grâce à la relation de récurrence, que la fonction c est croissante. Ainsi, si 2pn < 2p+1, alors 2p (p + 1) / 2 ≤ c(n) ≤ 2p+1 (p + 2) / 2.

En utilisant la croissance de la fonction logarithme, on en déduit la double inégalité

(n ln n) / (4 ln 2) ≤ c(n) ≤ n (ln n + 2 ln 2) / ln 2,

ce qui prouve que c(n) est de l’ordre de grandeur de n ln n.

 


Cet article est extrait d'un dossier complet et passionnant sur les nombres complexes publié dans le numéro HS 63 du Magazine Tangente.

Le dossier complet en suivant ce lien : Les nombres complexes


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 
 
 
 
Dernières publications