NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 23/06/2020

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                      Brèves de Maths

      

  Calculs avancés

 

Débutants

Multiplication

MULTIPLICATION

 

Glossaire

Multiplication

 

 

INDEX

 

Opérations

 

Calcul

TABLES

Tables vues autrement

Terminaisons

Calcul autour de 10

Calcul deux chiffres

Abaque / Boulier

Musulmane et...

Védiques

Avec les doigts

Décimales

Produits

Visuelles

Chiffre à chiffre

Pyramide

Grands nombres

 

 

Sommaire de cette page

>>> En bref

>>> Approche

>>> Multiplication classique itérative

>>> Algorithme de Karatsuba

>>> Algorithme de Toom-Cook

>>> Algorithme de Schönhage et Strassen

>>> Historique

 

 

 

 

 

 

MULTIPLICATION économe

des grands nombres

Algorithme de Karatsuba

 

Comment réaliser une multiplication avec de grands nombres le plus rapidement possibles avec un ordinateur. Quels sont les algorithmes ? Point des recherches sur ce sujet.

En 2019, une avancée théorique importante a été réalisée.

 

En bref

Brève 360

 

 

Approche

 

Quantité d'opérations élémentaires

Une multiplication de deux nombres de trois chiffres nécessite 3 x 3 = 9 multiplications et 4 ou 5 additions.

D'une manière générale une multiplication de deux nombres de n chiffres nécessite multiplications.

 

Est-il possible de réduire la quantité de ces multiplications ? Oui !

 

Un exemple de multiplication

 

Important: en calcul sur ordinateur, l'addition est simple et peu coûteuse; ce n'est pas le cas de la multiplication. D'où la recherche pour en minimiser la quantité.

 

Voir Multiplication posée

 

 

Multiplication classique itérative

 

Idée de calculs itératifs

Prenons un exemple avec la multiplication de deux nombres de quatre chiffres.

Le principe consiste à partager chaque nombre de quatre chiffres en deux nombres de deux chiffres.

Le produit est donné par la formule indiquée.

Il suffit alors d'appliquer cette formule à chacun des sous-produits de deux chiffres pour arriver à la multiplication de nombres à un seul chiffre.

 

Ex: 1 234 x 4 567

= 12 x 45 x 104

+ (12 x 67 + 34 x 45) x 102

+ 34 x 67

= 5 635 678

 

 

Les 16 multiplications élémentaires pour deux nombres de quatre chiffres

 

 

Algorithme de Karatsuba

 

Cette méthode reprend la méthode classique en arrangeant les termes de façon astucieuse, conduisant à trois multiplications élémentaires au lieu de quatre.

 

Anatoli Karatsoba (1937-2008) – mathématicien russe spécialiste de la théorie des nombres.

 

 

Ex: 1 234 x 4 567

= 12 x 45 x 104

+ (12 x 45 + 34 x 67 – (12 – 34) (45 – 67)) x 102

+ 34 x 67

= 5 635 678

 

Seulement 9 multiplications élémentaires pour deux nombres de quatre chiffres

 

 

Algorithme de Toom-Cook

Algorithme qui partage les opérandes en k éléments et les place comme coefficients de polynômes.

Le but est de retrouver les coefficients par résolution d'équations.

 

Exemple (simple!)

56 x 23

p(x) = 5x + 6 et qx = 2x + 3 avec x = 10

r(x) = p(x) q(x) = ax² + bx + c

Évidemment on peut calculer le produit du polynôme: r(x) = 10x² + 27x + 18 et donner le résultat de la multiplication: 10x100 + 27x10 + 18 = 1288

 

Avec de grands nombres, une autre méthode est plus économique: calcul des coefficients en résolvant un système d'équations, et cela, en choisissant des valeurs de x conduisant à des calculs simples.

 

Ici, on a formé un système d'équations en donnant les valeurs 0, 1 et -1 à x.

 

Implémentation de l'exemple avec la méthode Toom-Cook

 

 

 

Algorithme de Schönhage et Strassen

Avec cet algorithme, on change totalement de monde!

Comme souvent en mathématiques, on transpose le problème dans un autre monde pour utiliser des outils plus performants et, en fin de calcul, on revient dans le monde d'origine.

 

Une (petite) idée de l'algorithme

Dans ce cas, on calcule d'abord des convolutions et non des multiplications (en fait, des multiplications sans tenir compte des retenues).

 

Or, la convolution de deux éléments (vecteurs) peut être trouvée en faisant le produit des FFT*  des deux éléments, et en revenant en arrière en prenant la FFT inverse.

(* il s'agit des FFT discrètes, c'est-à-dire en numérique).

 

 

 

Historique

 

1962, Anatoly Karatsuba (russe)
Il trouve le moyen de réaliser l'opération avec n1,585 multiplications.

1963 et 1966, Andrei Toom et Stephen Cook améliore la méthode avec n1,46 : algorithme de Toom-Cook.

1971, Arnold Schönhage et Volker Strassen (allemands)
Ils arrivent à   n (log(n)) log(log(n)) multiplications
Avec des milliards de chiffres, la multiplication est réalisée en une demi-minute au lieu de 6 mois avec la méthode classique.

2013, Martin Fürer présente un algorithme dont la performance est en 2log n

 

 

2019, deux mathématiciens:

*      David Harvey, de l'Université de Nouvelle-Galles du Sud, en Australie, et

*      Joris van der Hoeven, de l'École Polytechnique

Algorithme de multiplication qui ne nécessite que n log (n) multiplications

N'est encore que théorique, mais il pourrait s'avérer d'une grande utilité pour optimiser la vitesse de calcul des ordinateurs et pour la programmation.

 

Principe:

Utilisation de la transformée de Fourier rapide (FFT).

En gros, la méthode consiste à couper les grands entiers que l'on veut multiplier en morceaux plus petits de taille environ log n. Grâce aux propriétés de la FFT, on ramène la multiplication des grands nombres à des multiplications sur des nombres de taille log n (si n vaut un milliard, log n est égal à environ 20,7).

 

J. van der Joeven et D. Harvey

 

Cependant cet algorithme n'est intéressant que pour de très, très grands nombres n > 21729^12

 

Hoeven cite cet exemple: avec un temps d'exécution d'une multiplication élémentaire d'une nanoseconde, une multiplication de deux nombres d'un milliard de chiffres prendrait: (109)² ns = 32 ans

 

L'algorithme connu de Schönhage-Strassen réduit ce temps à une trentaine de secondes sur un ordinateur ordinaire d'aujourd'hui. Avec le nouvel algorithme de 2019, la durée serait encore réduite.

 

 

 

 

 

Suite

*    Multiplications originales – Brève 278

*    Tables vues autrement

Voir

*    Calcul mental

*    Calcul védique

*    Initiation aux opérations

*    JeuxIndex

*    Nombres RSA

*    Multiplication

*    MultiplicationGlossaire

*    Multiplication des décimaux

*    Multiplications amusantes

*    Multiplications magiques

*    Multiplications pannumériques

*    Tables de multiplication

*    Théorie des nombres

Sites

*      Algorithme de Karasuba – Wikipédia

*      Algorithme de Toom-Cook – Wikipédia

*      La complexité de la multiplication – La Recherche – 10 avril 2019

*      Schönhage–Strassen algorithm* – Wikipedia – Pour se faire une idée

*    Faster integer multiplication** – Martin Fürer (pdf)

Cette page

http://villemin.gerard.free.fr/Calcul/MultGdNb.htm