Culture mathématique

Multiplication russe : multiplier sans les tables

Multiplication russe

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 !

La multiplication russe

Le fonctionnement de la multiplication russe

Reprenons les divisions successives par 2 en utilisant l’égalité euclidienne classique apprise au collège.

43=2\times 21+1

21=2\times 10+1

10=2\times 5

5=2\times 2+1

2=2\times 1

En remontant ces égalités une par une de haut en bas on arrive à ceci :

2=2\times 1

5=2\times 2\times 1+1

10=2\times(2\times 2\times 1 +1)=2^3+2

21=2\times (2^3+2)+1=2^4+2^2+1

43=2\times(2^4+2^2+1)+1=2^5+2^3+2+1

En se souvenant que 2=2^1 et 1=2^0 on arrive à 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

Du binaire au décimal et réciproquement !

L’écriture décimale à laquelle nous sommes habituée consiste à décomposer un nombre en puissance de 10. Par exemple :

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 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 2016=1024+512+256+128+64+32=2^{10}+2^9+2^8+2^7+2^6+2^5

Ou encore

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

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é :

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

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  75=75\times 2^0
 21  150=75\times 2^1
 10  300=75\times 2^2
 5  600=75\times 2^3
 2  1200=75\times 2^4
 1 2400=75\times 2^5

 

Le mystère est donc ainsi levé sur ce bel algorithme : la multiplication russe !

3 réflexions au sujet de « Multiplication russe : multiplier sans les tables »

  1. Bonjour,

    Je n’ai pas suivi dans le détail la démonstration de la technique de multiplication russe car ce n’était pas mon objectif (et je la trouve très “coûteuse” en temps) mais je pense que vous m’avez permis de répondre à la question que je me posais. Je suis enseignante ; il y a dans ma classe un jeune garçon russe qui vient d’arriver en France, il a 10 ans et il m’affirme qu’en Russie, on apprend pas les tables de multiplication. A la lumière de votre article, je pense que c’est vrai. Pouvez-vous me le confirmer ?

    Merci par avance,

    Sophie

Laisser un commentaire