Il existe de nombreux algorithmes pour calculer le produit de deux nombres. Celui que l’on apprend à l’école utilise l’écriture décimale, unité, dizaine, centaine… pour obtenir le résultat final. La multiplication russe qui s’inspire d’une méthode égyptienne consiste à décomposer l’un des deux facteurs en puissances de 2, ce qu’en langage moderne on appelle l’écriture binaire. Ainsi seule la connaissance des doubles et des moitiés est nécessaire. Voilà une méthode parfaite pour les obstinés qui refusent d’apprendre quelques tables.
La méthode de la multiplication russe
Effectuons pour apprendre le produit de 43 par 75.
Nous allons compléter le tableau suivant dans lequel nous allons diviser le plus petit facteur, 43, successivement par 2, sans tenir compte des parties décimales. Dans le même tableau on multiplie le plus grand facteur par 2.
| Divisions par 2 | Multiplication par 2 |
| 43 | 75 |
| 21 | 150 |
| 10 | 300 |
| 5 | 600 |
| 2 | 1200 |
| 1 | 2400 |
Il ne reste plus qu’à additionner les nombres de la deuxième colonne qui correspondent à des nombres impairs de la première colonne.
2400+600+150+75=3225
Vous pouvez vérifier… ça marche !
Le fonctionnement de la multiplication russe
Reprenons les divisions successives par 2 en utilisant l’égalité euclidienne classique apprise au collège.
$latex 43=2\times 21+1$
$latex 21=2\times 10+1$
$latex 10=2\times 5$
$latex 5=2\times 2+1$
$latex 2=2\times 1$
En remontant ces égalités une par une de haut en bas on arrive à ceci :
$latex 2=2\times 1$
$latex 5=2\times 2\times 1+1$
$latex 10=2\times(2\times 2\times 1 +1)=2^3+2$
$latex 21=2\times (2^3+2)+1=2^4+2^2+1$
$latex 43=2\times(2^4+2^2+1)+1=2^5+2^3+2+1$
En se souvenant que $latex 2=2^1$ et $latex 1=2^0$ on arrive à $latex 43=2^5+2^3+2^1+2^0$
Les habitués des mathématiques reconnaîtront ici l’écriture binaire de 43
Quelques mots sur les écritures binaires et décimales
L’écriture décimale à laquelle nous sommes habituée consiste à décomposer un nombre en puissance de 10. Par exemple :
$latex 2016=2\times 1000+0\times 100+1\times 10+6\times 1$
Ce qu’en sixième nous disions 2 unités de mille, 0 centaine, 1 dizaine et 6 unités.
Ainsi $latex 2016=2 \times 10^3+0 \times 10^2+1\times 10^1+6 \times 10^0$
Il suffit de passer des puissances de 10 au puissances de 2 pour passer du décimal au binaire.
Ainsi $latex 2016=1024+512+256+128+64+32=2^{10}+2^9+2^8+2^7+2^6+2^5$
Ou encore
$latex 2016=1\times 2^{10}+1\times 2^9+1\times 2^8+1\times 2^7+1\times 2^6+1\times 2^5+0\times 2^4+0\times 2^3+0\times 2^2+0\times 2^1+0\times 2^0$
2016 va donc s’écrire 11111100000 en binaire
Les divisions successives de 43 par 2 nous ont finalement donné l’écriture binaire de 43
$latex 43=2^5+2^3+2^1+2^0$ soit 101011 en binaire.
D’aileurs en reprenant la première colonne du tableau et en plaçant dans la seconde colonne un 1 quand le nombre est impair et 0 quand il est pair ( les restes de la division par 2 ), on obtient du bas vers le haut l’écriture binaire de 43. C’est un algorithme assez pratique pour passer du décimal au binaire !
| Divisions par 2 | Pair ou impair |
| 43 | 1 |
| 21 | 1 |
| 10 | 0 |
| 5 | 1 |
| 2 | 0 |
| 1 | 1 |
43 s’écrit bien 101011 en binaire, du bas vers le haut !
Mais oublions un peu le binaire maintenant…
Retour au produit de 43 par 75
Le produit de 43 par 75 va devenir plus simple maintenant avec un peu de distributivité :
$latex 43 \times 75=(2^5+2^3+2^1+2^0) \times 75=2^5\times 75+2^3\times 75+2^1\times 75+2^0\times 75$
$latex 43 \times 75=32\times 75+8\times 75+2\times 75+1\times 75=2400+600+150+75$
On comprend alors que la seconde colonne du tableau multiplie successivement 75 par 2, 4, 8, 16, 32… les puissances de 2.
Pour être un peu plus précis :
| Divisions par 2 | Multiplication par 2 |
| 43 | $latex 75=75\times 2^0$ |
| 21 | $latex 150=75\times 2^1$ |
| 10 | $latex 300=75\times 2^2$ |
| 5 | $latex 600=75\times 2^3$ |
| 2 | $latex 1200=75\times 2^4$ |
| 1 | $latex 2400=75\times 2^5$ |
Le mystère est donc ainsi levé sur ce bel algorithme : la multiplication russe !
Laisser un commentaire