Multiplication Russe

Connaissez-vous cette algorithme connu par les Egyptiens en 2000 avant JC, et qui fut aussi appelé la multiplication paysanne ?


Il s'agit ici de faire la multiplication de 2 nombres, sans connaître ses tables de multiplication. Il suffit pour cela de savoir diviser par 2 et multiplier par 2...

Dans la colonne A, on inscrit le plus grand des 2 nombres et en dessous, la partie entière des quotients successifs de la division par 2 jusqu'à l'unité. Dans la colonne B, on inscrit le plus petit puis en dessous les produits successifs de la multiplication par 2. Dans la colonne C, ajoutée à des fins d'illustration, on reporte les nombres de B qui sont associés à un nombre impair en A. La somme des nombres de la colonne C est le produit de 35 × 19, soit 665.

A B C
35 19 19
17 38 38
8 76 --
4 152 --
2 304 --
1 608 608
665

 
 
~cillbq~ Publié le : 26/09/2005

 

En cas de conflit avec cet article (problème de droits d'auteur, etc.) vous pouvez en demander la suppression auprès d'un administrateur du site.

N'y aurait-il pas une relation entre cette multiplication et l'article sur les logarithmes népériens? La colonne A aurait-elle un rapport avec les primitives et la colonne B avec les exponentielles? Je ne suis que novice en la matière et je m'émerveille de toutes les connaissances présentes sur ce site, je tenais seulement à faire part d'une possible corrélation qui m'a troublé, j'attends le commentaire d'un expert qui pourra la rendre (si elle existe vraiment...) plus claire...

~Syrius~ le 13-01-2007 à 00:00
 

« La colonne A aurait-elle un rapport avec les primitives et la colonne B avec les exponentielles? »

A première vue, le rapport qu'on pourrait entrevoir ça serait que les solutions de df(x)/dx = 2.f(x) est f: x -> A.exp(2.x)

Mais bon, en fait c'est juste une histoire toute bête de multiplication et de divisions, pour s'en rendre compte il suffit de décortiquer l'algorithme :

On va commencer par noter : A_i, B_i, C_i les A, B et C respectivement après la i-ème itération de l'algorithme. Ainsi par convention, A_0 = A (puisqu'on a encore rien fait.)

Bon, regardons ce qui se passe lorsqu'on effectue une itération :

A_i+1 = E(A_i/2)
Où E désigne la fonction partie entière :
E(x) est l'entier n tel que : n ≤ x < n+1

B_i+1 = 2.B_i

Regardons ce qui se passe lorsque A_i est paire, alors :
E(A_i/2) = A_i/2 (puisque ça sera un entier), et donc A_(i+1).B_(i+1) = A_i.B_i
On ne perd pas d'informations.

Par contre lorsque A_i est impaire, alors :
A_i.B_i = (E(A_i/2) + 1/2)(2.B_i)
C'est pourquoi, on garde en mémoire dans C_i : (1/2).(2.B_i), autrement dit B_i.

Enfin on vérifie si le test d'arrêt est valide (c'est à dire que A_i atteindra forcément 1) :
Pour que (A_i) (la suite des A_i) ne passe pas par 1 et saute directement à 0 (puisque le numérateur et le dénominateur sont positifs, on n'ira jamais dans les négatifs), il faudrait que 0 ≤ A_i+1 < 1, c'est à dire :
0 ≤ A_i/2 < 1
0 ≤ A_i < 2

Donc pour sauter 1, il faudrait que A_i passe par … 1, ce qui est justement le test d'arrêt.

Enfin on vérifie que le résultat est bon, on note n le rang d'arrêt de l'algorithme, alors :
A_n = 1
A.B =1.B_n + Somme des C_i
Si on applique une dernière fois, vu que 1 est impair, on obtient :
A.B = Somme de i = 0 à n+1 des C_i
C'est bien ce qu'est censé trouver l'algorithme. On est content.

Mais bon, là je m'éloigne quand même un peu du sujet, et tu avais demandé s'il n'existait pas une corrélation entre cette méthode et les fonctions ln et exp.
Et bien il y en a une qui se cache … dans la complexité de l'algorithme suivant la multiplication :
L'algorithme s'arrête quand A/2^n < 1
C'est à dire : A < 2^n
On passe aux logarithmes :
ln(A) < n.ln(2)
n > log_2(A)
Mais bon, cette approximation est imprécise puisque les divisions successives de A font intervenir des critères de divisibilités, donc ça touche aux nombres premiers, donc ça devient vite chaotique.
Dans le pire des cas, A est sous la forme 2^(n+1) - 1, qui fait qu'à chaque division on aura une addition supplémentaire à effectuer, la complexité se voit incrémenter d'un facteur n (divisé par une constante étant donné que les multiplications ne valent pas les additions en terme de temps de calcul).
De même, les multiplications seront plus rapide, car équivalentes à une addition …

À titre de comparaison, l'algorithme de Karatsuba, qui correspond à notre multiplication faite main est de complexité en n^log_2(3), ce qui est déjà très bien, mais appliqué à nos petites mains, c'est moins efficace au niveau facilité vu que ce sont des "vraies" multiplications et non pas juste a+a.
Mais en même temps, il n'y a pas de division...
Et en terme de complexité mémoire (où ici la mémoire est la feuille de brouillon), c'est sûr que l'algorithme de poser est plus efficace.

Pour information, dans une machine, c'est un algorithme basé sur la transformée de Fourier rapide qui est utilisé, est qui est en n.ln.ln(ln).

Voilà, j'espère t'avoir éclairé, et j'espère que la date est erronée, parce que si t'as attendu depuis 2007 pour avoir cette réponse...

~Lebensbringer~ le 09-09-2011 à 22:57
 
1

Il faut être membre du site afin de pouvoir débattre autour d'un article.