Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Technique de multiplication dite russe
Résumé
La technique de multiplication dite russe consiste à diviser par 2 le multiplicateur (et ensuite les quotients obtenus), jusqu'à un quotient nul, et à noter les restes ; et à multiplier parallèlement le multiplicande par 2. On additionne alors les multiples obtenus du multiplicande correspondant aux restes non nuls.
Cela revient en fait à écrire le multiplicateur en base 2 et à faire ensuite des multiplications par 2 et des additions. C'est donc une variante de la technique de la multiplication en Égypte antique, bien qu'elle ait pu être redécouverte indépendamment.
En pseudo code, l'algorithme de multiplication dite russe peut s'écrire :
Fonction mult (x,y)
r = 0
Tant que x est différent de 0
Si x est impair alors
r = r + y
x = x - 1
fin si
x = x / 2
y = y * 2
Fin tant que
Renvoyer r
Fin fonction
Note : les opérations effectuées ici sont des opérations sur des entiers et sont à valeurs dans les entiers.
Pour 13 x 238 on peut écrire :
13 = 1101 en base 2 (obtenu en lisant les restes de bas en haut dans le tableau, et écrit selon la convention usuelle de droite — unités — à gauche — puissances élevées).
Pour limiter le nombre d'opérations, il faut généralement choisir comme multiplicateur le plus petit des deux nombres à multiplier. Toutefois, si l'un d'eux est une puissance de 2, c'est plutôt lui qu'il faut préférer (il n'y a pas d'addition).
Les restes deviennent forcément nuls, et donc le résultat devient stable, à partir du moment où le quotient est lui-même nul. Formellement, la condition d'arrêt (s'arrêter lorsque le quotient est nul) est donc seulement une commodité.
Graphiquement, l'on peut dire qu'une multiplication transforme un rectangle multiplicateur x multiplicande en une ligne en conservant le nombre d'éléments.
L'algorithme graphique consiste pour la multiplication russe à :
a) si le multiplicateur est pair, prendre la moitié inférieure du rectangle et la coller sur un côté (on transforme ainsi un rectangle 2n x p en un rectangle n x 2p) ; b) si le multiplicateur est impair, enlever d'abord la dernière ligne et la mettre à part, ce qui ramène au cas précédent 1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.