L'algorithme de Doraki pour multiplier deux nombres de façon originale
Anthony Canu nous présente en vidéo l'algorithme très original de Doraki pour multiplier deux nombres. J'ai réussi à le faire tourner... donc vous n'aurez aucun problème à le faire.
J'ai commencé par 23x52 qui est très simple et j'ai ensuite testé avec 32x52. Le 32 se transforme en 4-8.
Cette vidéo vous présente une méthode particulière permettant de multiplier des grands nombres sans utiliser les tables de multiplication. Cette vidéo est un prolongement de la vidéo précédente
Elle permet de multiplier des entiers plus gros grâce à l'algorithme de Doraki.
Cet algorithme est une réponse simple à un problème mathématique compliqué :
Réécrire un entier N comme une somme de termes de la forme ϵ×k×10^j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N et pour laquelle le nombre de tels termes est minimal.
Cet algorithme a été créé le 10.03.16 par Doraki à l'issue d'une discussion sur le forum Maths Forum :
http://www.maths-forum.com/superieur/...
L' algorithme peut se présenter ainsi :
***************************************
Prendre un par un les chiffres de la multiplicande de la droite vers la gauche en commençant par le chiffre situé le plus à droite :
Si le chiffre est un 0,un 1 ou un 4, il reste inchangé et vous passez au chiffre suivant.
Si le chiffre est un 2, vous regardez la parité du chiffre suivant : s'il est pair alors le chiffre 2 reste inchangé, si le chiffre suivant est impair alors le chiffre 2 devient (-8) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 3, vous regardez la parité du chiffre suivant : s'il est pair alors le chiffre 3 reste inchangé, si le chiffre suivant est impair alors le chiffre 3 devient (-7) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 5, vous regardez la parité du chiffre suivant : s'il est pair alors le chiffre 5 reste inchangé, si le chiffre suivant est impair alors le chiffre 5 devient (-5) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 6 alors il deviendra (-4) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 7, vous regardez la parité du chiffre suivant : s'il est pair alors le chiffre 7 reste inchangé, si le chiffre suivant est impair alors le chiffre 7 devient (-3) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 8, vous regardez la parité du chiffre suivant : s'il est pair alors le chiffre 8 reste inchangé, si le chiffre suivant est impair alors le chiffre 8 devient (-2) et on ajoutera alors une retenue de 1 au chiffre suivant.
Si le chiffre est un 9 alors il deviendra (-1) et on ajoutera alors une retenue de 1 au chiffre suivant.
En résumé :
************
0,1 ou 4 restent inchangés
6 devient (-4) et 9 devient (-1) toujours
2 devient (-8) et 8 devient (-2) et 3 devient (-7) et 7 devient (-3) et 5 devient (-5) si le chiffre suivant est impair sinon restent inchangés
Quand on transforme un chiffre en négatif, on oublie pas d'ajouter une retenue de 1 au chiffre suivant !
Compléments de l'auteur:
Inspiré par la multiplication russe et égyptienne, j'ai essayé de créer il y a 6 ans une méthode permettant de multiplier 2 entiers avec la contrainte suivante : Ne pas utiliser les tables de multiplication.
Je suis parvenu à ceci :
L'efficacité (en terme de temps d'exécution) de cette méthode dépend des entiers à multiplier. Plus leurs digits seront constitués de puissance de deux et plus la méthode sera efficace.
Et si il existait une façon de réécrire les entiers à multiplier pour faire apparaître un maximum de puissance de 2 ?
Après un long moment de réflexion, j'ai publiquement posé le problème ainsi :
Je cherche l'écriture d'un entier N sous la forme d'une somme de termes de la forme ϵ×k×10^j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N et pour laquelle le nombre de tels termes est minimal.
Exemples :
---------------
139 = 100+20+10+8+1 (réécriture brute en cinq termes)
139 = 100+40-1 (réécriture optimale en trois termes)
157 = 100+40+10+4+2+1 (réécriture brute en six termes)
157 = 200-43 = 200-40-2-1 (réécriture optimale en quatre termes)
87 = 80+4+2+1 (réécriture brute en quatre termes)
87 = 80+8-1 (réécriture optimale en trois termes)
38 = 20+10+8 (réécriture brute en trois termes)
38 = 40-2 (réécriture optimale en deux termes)
Exemples :
---------------
139 = 100+20+10+8+1 (réécriture brute en cinq termes)
139 = 100+40-1 (réécriture optimale en trois termes)
157 = 100+40+10+4+2+1 (réécriture brute en six termes)
157 = 200-43 = 200-40-2-1 (réécriture optimale en quatre termes)
87 = 80+4+2+1 (réécriture brute en quatre termes)
87 = 80+8-1 (réécriture optimale en trois termes)
38 = 20+10+8 (réécriture brute en trois termes)
38 = 40-2 (réécriture optimale en deux termes)
Les réponses que j'ai pu obtenir sont assez surprenantes :
1/ Oui il existe une telle réécriture (optimale) et cette dernière n'est pas unique. Plusieurs décompositions peuvent amener à la réécriture optimale.
2/ Il existe des algorithmes permettant d'aboutir à une telle décomposition :
Algorithme de Bolza :
------------------------------
On sait que les chiffres possibles sont 1,2,4 et 8.
donc j'encadre d'abord le nombre entre deux nombres de la forme 1*10^k, 2*10^k, 4*10^k ou 8*10^k et je prend la valeur la plus proche.
Par exemple, avec 497 537 :
on a 400 000 <= 497 537 <= 800 000
comme 497 537 est plus proche de 400 000 que de 800 000 je choisis 400 000 :
497 537 = 400 000 + 97 537.
ensuite 80 000 <= 97 537 <= 100 000
comme 97 537 est plus proche de 100 000 que de 80 000, je choisis 100 000 :
497 537 = 400 000 + 100 000 - 2463
2463 est plus proche de 2000 que de 4000 donc :
497 537= 400 000 + 100 000 - 2000 - 463.
463 est plus proche de 400 que de 800 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 63.
63 est plus proche de 80 que de 40 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 17.
17 est plus proche de 20 que de 10 :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 20 - 3.
donc j'encadre d'abord le nombre entre deux nombres de la forme 1*10^k, 2*10^k, 4*10^k ou 8*10^k et je prend la valeur la plus proche.
Par exemple, avec 497 537 :
on a 400 000 <= 497 537 <= 800 000
comme 497 537 est plus proche de 400 000 que de 800 000 je choisis 400 000 :
497 537 = 400 000 + 97 537.
ensuite 80 000 <= 97 537 <= 100 000
comme 97 537 est plus proche de 100 000 que de 80 000, je choisis 100 000 :
497 537 = 400 000 + 100 000 - 2463
2463 est plus proche de 2000 que de 4000 donc :
497 537= 400 000 + 100 000 - 2000 - 463.
463 est plus proche de 400 que de 800 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 63.
63 est plus proche de 80 que de 40 donc :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 17.
17 est plus proche de 20 que de 10 :
497 537 = 400 000 + 100 000 - 2000 - 400 - 80 + 20 - 3.
Algorithme de Doraki
-----------------------------
il y aurait une stratégie optimale super simple, qui décide de quelles unités (1,2,4,8) on prend en regardant n mod 20 (une fois qu'on a décidé quelles unités on prenait, on divise le reste par 10 et on recommence)
La table :
0 mod 10 -> 0
1 mod 10 -> 1
02 mod 20 -> 2
12 mod 20 -> -8
03 mod 20 -> 3 (1+2)
13 mod 20 -> -7 (1-8)
4 mod 10 -> 4
05 mod 20 -> 5 (1+4)
15 mod 20 -> -5 (-1-4)
6 mod 10 -> -4
07 mod 20 -> 7 (8-1)
17 mod 20 -> -3 (-1-2)
08 mod 20 -> 8
18 mod 20 -> -2
9 mod 10 -> -1
Si je lis bien, ça revient à aller au multiple de 10 le plus proche, et si il y a égalité, aller à celui qui est un multiple de 20.
La table :
0 mod 10 -> 0
1 mod 10 -> 1
02 mod 20 -> 2
12 mod 20 -> -8
03 mod 20 -> 3 (1+2)
13 mod 20 -> -7 (1-8)
4 mod 10 -> 4
05 mod 20 -> 5 (1+4)
15 mod 20 -> -5 (-1-4)
6 mod 10 -> -4
07 mod 20 -> 7 (8-1)
17 mod 20 -> -3 (-1-2)
08 mod 20 -> 8
18 mod 20 -> -2
9 mod 10 -> -1
Si je lis bien, ça revient à aller au multiple de 10 le plus proche, et si il y a égalité, aller à celui qui est un multiple de 20.
Exemple :
1789
on commence par la droite
9 devient -1
8 devient 9 (retenue du chiffre précédent) qui devient -1
7 devient 8 (retenue du chiffre précédent) qui devient -2 car le chiffre suivant est impair
1 devient 2 (retenue du chiffre précédent)
1789 = 2(-2)(-1)(-1) = 2000-200-10-1 (écriture optimale)
Ainsi il est toujours possible de réécrire un entier à l'aide d'une somme de termes de la forme ϵ×k×10^j où ϵ∈{−1,1}, k∈{1,2,4,8} et j∈N et pour laquelle le nombre de tels termes est minimal.
Si on prend au hasard un nombre de n chiffres et qu'on calcule la longueur moyenne de la décomposition, normalement on obtient quelque chose équivalent à 56*n/55.
Donc le "coût moyen d'un chiffre" est de 56/55 = 1.0181818...
Donc le "coût moyen d'un chiffre" est de 56/55 = 1.0181818...
Preuve :
-----------
soit Xn : le coût total pour décomposer tous les entiers de 0 à (10^n)-1 en pouvant laisser un éventuel 10^n
Yn : le nombre de cas où on laisse un 10^n inconditionnellement
Zn : le nombre de cas où on laisse un 10^n si le chiffre suivant est impair
X1 = 12 ; Y1 = 2 ; Z1 = 5
Pour calculer X (n+1), on a déjà besoin de 10*Xn pour retirer tous les trucs mod 10^n ; et on se retrouve avec un d*10^n où d a la distribution suivante :
0 * (10^n-Yn)
1,3,5,7,9 * (10^n-Zn)
2,4,6,8 * (10^n+Zn)
10 * (Yn+Zn)
Le coût est de 1 pour d=1,2,4,6,8,9 et de 2 pour d=3,5,7,
On a donc X (n+1) = 10*Xn + 12*10^n - 4 * Zn
On se retrouve automatiquement avec un 10^(n+1) lorsque d=6,9,10 donc Y(n+1) = Yn+Zn+2*10^n
et conditionnellement selon la parité du chiffre suivant lorsque d=2,3,5,7,8 donc Z(n+1) = -Zn + 5*10^n
Le coût total est de Xn + Yn
X0 = 0 ; Y0 = 0 ; Z0 = 0 --> 0
X1 = 12 ; Y1 = 2 ; Z1 = 5 --> 14
X2 = 220 ; Y2 = 27 ; Z2 = 45 --> 247
X3 = 3220 ; Y3 = 272 ; Z3 = 455 --> 3492
...
On prouve facilement que Zn = (5/11) * (10^n - (-1)^n) ,
puis que Yn = (-11 + 6* 10^n + 5* (-1)^n) /22
puis que Xn = (56/55) * n*10^n + (20/121) * (10^n - (-1)^n)
Donc finalement le cout total est Xn+Yn = (-1/2) + (56/55) * n*10^n + (53/121)*10^n + (15/242)*(-1)^n
Yn : le nombre de cas où on laisse un 10^n inconditionnellement
Zn : le nombre de cas où on laisse un 10^n si le chiffre suivant est impair
X1 = 12 ; Y1 = 2 ; Z1 = 5
Pour calculer X (n+1), on a déjà besoin de 10*Xn pour retirer tous les trucs mod 10^n ; et on se retrouve avec un d*10^n où d a la distribution suivante :
0 * (10^n-Yn)
1,3,5,7,9 * (10^n-Zn)
2,4,6,8 * (10^n+Zn)
10 * (Yn+Zn)
Le coût est de 1 pour d=1,2,4,6,8,9 et de 2 pour d=3,5,7,
On a donc X (n+1) = 10*Xn + 12*10^n - 4 * Zn
On se retrouve automatiquement avec un 10^(n+1) lorsque d=6,9,10 donc Y(n+1) = Yn+Zn+2*10^n
et conditionnellement selon la parité du chiffre suivant lorsque d=2,3,5,7,8 donc Z(n+1) = -Zn + 5*10^n
Le coût total est de Xn + Yn
X0 = 0 ; Y0 = 0 ; Z0 = 0 --> 0
X1 = 12 ; Y1 = 2 ; Z1 = 5 --> 14
X2 = 220 ; Y2 = 27 ; Z2 = 45 --> 247
X3 = 3220 ; Y3 = 272 ; Z3 = 455 --> 3492
...
On prouve facilement que Zn = (5/11) * (10^n - (-1)^n) ,
puis que Yn = (-11 + 6* 10^n + 5* (-1)^n) /22
puis que Xn = (56/55) * n*10^n + (20/121) * (10^n - (-1)^n)
Donc finalement le cout total est Xn+Yn = (-1/2) + (56/55) * n*10^n + (53/121)*10^n + (15/242)*(-1)^n
Aux regards de ces éléments, il apparaît clairement que pour n suffisamment grand, la multiplication (à la main) de deux entiers de n chiffres est moins longue à réaliser avec cette méthode qu'avec la méthode classique (celle enseignée dans les écoles) utilisant les tables de multiplication.
Preuve :
-----------
Une multiplication "classique" de 2 entiers de n chiffres nécessite de réaliser n*n multiplications élémentaires puis de réaliser une addition de n entiers constitués de (n+1) chiffres chacun.
Une multiplication avec la méthode présentée ici nous conduit à réaliser /une addition de 2 entiers de n chiffres (obtention de la multiplication par 2 du multiplicateur) puis 2 entiers de (n+1) chiffres (obtention de la multiplication par 4 du multiplicateur) puis 2 entiers de (n+1) chiffres (obtention de la multiplication par 8 du multiplicateur)
/une réécriture du multiplicande à l'aide de l'algorithme de Doraki (se fait instantanément de tête en prenant les digits de la droite vers la gauche)
/ une addition de (56/55)*n entiers constitués de (n+1) chiffres chacun
En comparant le temps d'exécution des deux méthodes, on se rend vite compte que pour n suffisamment grand, la différence ne se situe pas sur l'addition finale "celle donnant le résultat de la multiplication" (addition de n entiers constitués de (n+1) chiffres chacun VS addition de (56/55)*n entiers constitués de (n+1) chiffres chacun ) mais sur l'obtention des termes constituant l'addition finale (n² VS (4*n+2))
A partir de n=5 chiffres, la multiplication de deux entiers de n chiffres (pris au hasard) par la méthode classique commence à devenir plus longue à réaliser à la main qu'en utilisant la méthode présentée ici.
Autrement dit, plus la valeur de n augmente et plus la différence s'accentue entre les deux méthodes :)
Commentaires
Merci pour ce partage et bon courage à tous ceux qui souhaitent apprendre cette méthode. Je reste disponible si vous rencontrez quelques difficultés et/ou souhaitez obtenir des informations complémentaires.