Technique de multiplication dite russe

La technique de multiplication dite russe consiste à diviser par 2 le multiplicateur, jusqu'à un quotient nul, ainsi qu'à noter les restes ; ainsi qu'à multiplier parallèlement le multiplicande par 2.



Catégories :

Calcul manuel - Mathématiques élémentaires

Recherche sur Google Images :


Source image : fr.wikipedia.org
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Multiplication russe - Prolongement par continuité. (TS2) - Multiplication russe (suite) - TS3 mais également les ... Il reste juste à formaliser légèrement ce qui a déjà été dit.... Voici la justification de cette technique de multiplication.... (source : mathiroise.over-blog)
  • Effectuer un décalage binaire à gauche, revient à multiplier ce... il s'agit de la multiplication dite à la Russe découvert par les anciens... Vos questions techniques : forum d'entraide Assembleur - Publiez vos articles... (source : developpez)

La technique de multiplication dite russe consiste à diviser par 2 le multiplicateur (et ensuite les quotients obtenus), jusqu'à un quotient nul, ainsi qu'à noter les restes ; ainsi qu'à 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 ainsi qu'à faire ensuite des multiplications par 2 et des additions. C'est par conséquent une variante de la technique de la multiplication en Égypte antique, quoiqu'elle ait pu être rédécouverte indépendamment.

Exemple

13 x 238 on écrit

13/2 = «quotient» 6 reste 1, 238, 238
6/2 = «quotient» 3 reste 0, (476 pour mémoire), 238
3/2 = «quotient» 1 reste 1, 952, 1190
1/2 = «quotient» 0 reste 1, 1904 (stop : le quotient est nul), 3094

13 x 238 = 3094

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 le plus souvent choisir comme multiplicateur le plus petit des deux nombres à multiplier. Cependant, 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 nécessairement nuls, et par conséquent 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 quand le quotient est nul) est par conséquent uniquement une commodité.

Algorithme graphique

Graphiquement, 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 à :

  1. 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 en premier lieu la dernière ligne et la mettre à part, ce qui ramène au cas précédent 1. a)  ;
  2. recommencer jusqu'à n'obtenir qu'une seule ligne ;
  3. additionner l'ensemble des lignes mises à part.

Voir aussi

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Technique_de_multiplication_dite_russe.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu