Une multiplication pharaonique (ta mère ! Désolé...)

[kweeky]

Salut

Etant en déplacement avec mon Sharp PC-1403, mon Casio 730P (merci ledudu !) et le numéro Hors Série n°54bis de l'Ordinateur Individuel, que pouvais-je bien faire ?

Après lecture de l'article des pages 133 et 134, consacré à une méthode de multiplication que je ne connaissais pas et (parait-il) utilisée par les égyptiens, je décidais de sortir mes deux pockets. Pour ceux qui n'ont pas ce bouquin à leur disposition, sachez qu'on peut le télécharger sur le très bon site abandonware-magazine. Sinon, je vous mets la page correspondante (je n'ai pas mis la page 134, avec le listing Basic, vous pourrez aller le chercher sur le site précité si ça vous intéresse) :

Cliquez ici

Tout d'abord, avant de parler pocket, je suis assez surpris que ce type d'algorithme ait été connu par les égyptiens, peuple très avancé s'il est vrai, mais certainement pas au niveau des mathématiques. Le système même de numération égyptien, de nature additive, un peu comme celui des romains plus tard, ne permet pas de "poser" correctement et pratiquement des opérations. Les égyptiens ne connaissaient pas le système de numération positionnel, or l'algorithme décrit dans cet article présuppose une connaissance de cet ordre, car en fait, cela revient à travailler en binaire. (Je vous laisse chercher un peu, je reviendrai là dessus si besoin est). En même temps, je ne prétend pas être un historien accompli. Donc si quelqu'un a des éclaircissements, je suis preneur !

L'algo est simple. Mais j'ai essayé de faire le plus court possible (au détriment de l'efficacité), genre deuligne. Grâce aux spécificités du Basic Sharp, j'ai même pu faire une version "monoligne", totalisant 60 octets :

Code : Tout sélectionner

1 INPUT A,B:P=0:FOR I=0 TO LN A/LN 2:C=A/2:P=P+B*(C<>INT C):A=INT C:B=B*2:NEXT I:PRINT P

Je vous conseille de tout taper sans espaces, la longueur de la ligne est "limite" sinon.

A cause du fait que les Casio ne connaissent pas les variables booléennes (Honte sur eux !), on est obligé de faire un test, et on se retrouve avec deux lignes, pour une version faisant 59 octets :

Code : Tout sélectionner

1 INPUT A,B:P=0:FOR I=0 TO LN A/LN 2:C=A/2:IF C<>INT C THEN P=P+B
2 A=INT C:B=B*2:NEXT I:PRINT P

Attention, le "<>" de la ligne 1 doit être remplacé par le symbole "égale barré" que je ne sais pas faire ici.

On voit que les versions Casio et Sharp ne se font pas mal au niveau taille mémoire. Au niveau rapidité, j'ai trouvé qu'étrangement les deux machines allaient pratiquement à la même vitesse (avec une toute petite avance pour le Casio, mais à peine).

A vous de jouer. Pouvez-vous faire plus court, tout modèles confondus (pas seulement Pockets Basic) ? Sauriez-vous faire une version monoligne sur le Casio ?

@+

P.S.: pour ceux qui se poseraient LA question : à quoi ça sert ? La réponse est simple : 42 ! Ceux qui veulent une réponse plus précise, là voilà : "il faut bien s'occuper en attendant la mort", dixit Desproges.

[Marge]

Rapidement, car je n'ai même pas lu ton article (ô combien intéressant) en entier, il est probable qu'on fasse allusion à l'Egypte ptolémaïque (ta mère !), plus tardive et surtout d'origine (ou plus justement, d'influence) grecque - à vérifier, cependant.

[kweeky]

Salut Marge,

Effectivement, une influence grecque pourrait expliquer cela, les grecs possédant un système de numération positionnel. Tu m'as donné envie de me replonger dans mes bouquins d'histoire !

@+

[treza]

Je connaissais cette technique par l'appellation "à la russe"

Wikipédia-qui-sait-tout explique d'ailleurs le rapport entre la méthode russe et la méthode égyptienne.

http://fr.wikipedia.org/wiki/Technique_ ... dite_russe
http://fr.wikipedia.org/wiki/Technique_ ... te_antique

Evidemment, cette technique fut utilisé par les ordinateurs pour multiplier bit à bit.
Maintenant, on utilise beaucoup l'encodage de Booth, les arbres de Wallace.
Un cours superbienfoutu :
http://users-tima.imag.fr/cis/guyot/Cours/Arithmetique/

[Marge]

Et Pan sur le bec (comme on dit au Canard Enchaîné) !

1. Selon le Georges Ifrah (qui n'a pas son Georges Ifrah ? La Bible des nombres, Le Coran de l'algèbre, le Popol Vuh des systèmes numériques...), les Egyptiens en sont restés à leur numération un peu simple, inventée tout de même à l'aube de l'humanité (et décimale), durant leurs trois âges... Au point où j'en suis de ma lecture, il n'y a rien de l'influence des Grecs sur leur système de numération ; le nombre 20, par exemple, était représenté par deux faucons représentant chacun 10. Mais peut-être que le "système numérique égyptien" est considéré par l'auteur comme délimité par l'influence grecque.
2. Ptolémaïque (ta mère !), c'est quand même super nul. Algébrique (ta mère !) sonne mieux, mais je ne l'avais pas sous la main. Désolé

[C.Ret]

Salut,


Ce qui m'épate c'est qu'aucun d'entrevous ne semble s'être rendu compte que la technique de multiplication en question et justement dite "égyptienne" ou selon le "paysan russe" car justement elle ne nécessite pas de représentation décimal des nombres.

En fait, elle peut être utilisée indépendamment de la façon de représenter les nombres, qu'il s'agisse d'aigles, de nombres ou de petits pois, l'algorithme en question est utilisable:

On peut très bien faire la multiplication avec des petits-poids, par exemple 8 x 9 petits pois font :

[kweeky]

Ah oui, vu comme ça, ça parait simple ! Merci C.Ret

Il faut juste préciser qu'il y a parfois une petite complication, lorsque la division par 2 ne tombe pas juste.

Si on reprend ton exemple en faisant la multiplication à l'envers : 9 x 8 petits pois

A la première étape on a un carré de 9 lignes et 8 colonnes.

9 /2 = 4,5, donc on n'aura que 4 lignes de 16 colonnes, et il nous restera 8 petits pois, qu'il faudra compter dans le résultat. Or s'il y a ce reste, c'est bien parce que 9 est impair, donc on tient compte de 8.

Etage suivant, on a : 2 lignes de 32 colonnes.

Etages suivant, on a : 1 ligne de 64 colonnes.

Ce qui nous fait donc ben un résultat de 64 + 8 = 72 petits pois

Effectivement, on peut penser qu'historiquement c'est de cette façon là que la méthode a été mise au point. On a parfois du mal à penser "simple".

Merci en tout cas !

[Hobiecat]

En fait, elle peut être utilisée indépendamment de la façon de représenter les nombres, qu'il s'agisse d'aigles, de nombres ou de petits pois, l'algorithme en question est utilisable:

On peut aussi compter les TI-88 comme ça ?

Blague à part, c'est vrai qu'avec les dessins, tout s'explique... Merci !

[C.Ret]

Il faut juste préciser qu'il y a parfois une petite complication, lorsque la division par 2 ne tombe pas juste.

Et oui c'est ça l'astuce de l'algorithme en question, il faut accumuler le nombre de petit pois quand justemetn ça ne tombe pas juste.

Donc, effectivement si l'on considère 9 x 8, il est difficile de couper 9 en deux parts égales. Il y a donc une ligne de 8 petits pois qui restent.



Il y a une ligne "orpheline" qui fait donc justement 8 petits pois




Ensuite, on peut couper en deux jusqu'à obtenir 1x64. Le résultat est donc bien 64+8=72.


C'est un cas particulier. Si l'on avait trouver un nombre de lgne non divisible par deux il aurait été nécessaire d'accumuler "d'autres lignes orphelines".


P.S.: Je n'ai pas de mérite, il y a une ou deux semaine de cela, Gerson W. Barbosa proposait un mini-challenge sur le HP-Forum qui consister à écrire un programme RPN qui effectuait la multiplication de deux entiers sans utiliser la touche 'x'. Sa solution consiste justement à coder cet algorithme.

[Marge]

[edit modo] pas d'images aussi grandes, on met le lien, ça suffit [/edit modo]

Edith Midi: Ahouid'accordtrèsbienpasdeproblème.

http://img69.imageshack.us/img69/6058/egypte1.jpg
http://img593.imageshack.us/img593/2721/egypte2.jpg
http://img585.imageshack.us/img585/8731/egypte3.jpg

Edith : "ça devrait aller mieux" ; je veux vous montrer un extrait de cet ouvrage fabuleux de Georges Ifrah, l'Histoire universelle des chiffres. Ici, un extrait qui concerne nos Egyptiens et leur principe de doublage en guise de multiplication (et de division).

D'autre part, (au point où j'en suis de ma lecture) les Grecs n'auraient pas connu le principe de la numération de position - et en tout cas, ne l'auraient pas transmis aux Egyptiens - (pan sur le bec, IIème acte) : on devrait sa découverte accidentelle et tardive aux savants babyloniens, gênés d'avoir deux motifs identiques pour représenter l'unité et le 60 (en l'occurrence des clous), et finalement ayant recours à un déplacement du signe pour déterminer sa valeur et éviter les confusions (p. 353, Tome premier). D'autres sociétés ont pris le chemin de la numération de position, toujours comme par défaut, ou accident.

Les Indiens ont aussi découvert le principe de numération de position, amélioré, mais déjà à un âge avancé de l'ère chrétienne (600 ou 700 de notre ère si ma mémoire ne me joue pas de tour)..

C'est vraiment un bouquin que je recommande (2 tomes, plus de deux mille pages fascinantes à s'offrir ou se faire offrir).

[C.Ret]

Ha!

J'oubliais un détail, sur SHARP PC-1211, on peut faire un poil plus court :

Code : Tout sélectionner

1 INPUT A,B:P=0:FOR I=0 TO LN A/LN 2:C=A/2:P=P+B*(C<>INT C):A=INT C:B=B*2:NEXT I:PRINT P

devient

Code : Tout sélectionner

10 : INPUT A,B:P=0:FOR I=0 TO LN A/LN 2:A=INT A/2:P=P+(A<>INT A)B:B=2B:NEXT I:PRINT P

ce qui revient surtout à ce passer de la variable intermédiaire et transitoire 'C'. Il y a aussi deux multiplications implicite qui économisent chacune un signe '*'.

On peut aussi éviter la boucle FOR/NEXT et sa variable I, mais cela ne tient plus en une seule ligne:

Code : Tout sélectionner

1:INPUT A,B:P=0
2:A=INT A/2:IF A LET P=P+(A<>INT A)B,B=2B:GOTO 2
3:PRINT P

Et en adaptant sans l'astuce du test imbriqué dans une expression algébrique (comme pour les CASIO, mais aussi autre Pocket TI, Canon, etc ...)

Code : Tout sélectionner

1:INPUT A,B:P=0
2:A=INT(A)/2:IF A<>INT(A) THEN P=P+B
3:B=2*B:IF A>=1 THEN 2
4:PRINT P

[Marge]

Numérisation mise à jour.

[Hobiecat]

Numérisation mise à jour.

Je confirme, ça se "voit" maintenant !

[Gilles59]

En RPL sauce algébrique :

Code : Tout sélectionner

'Egypt(a,b,r)=IFTE(a==1,b+r,Egypt(IP(a/2), b+b, IFTE(FP(a/2),b+r,r)))' DEFINE

'Egypt(83,151,0)' EVAL
donne
12533 = 83*151

La fonction est récursive et suit complément la description de C.RET

Pour comprendre :

IFTE ( condition, action si vrai, action si faux)
IP retourne la partie entière
FP retourne la partie fractionnaire
== teste si les valeurs sont égales

je suppose que çà doit fonctionner même en "vieux RPL" sur les 28 et 48

Variante

Code : Tout sélectionner

'Egypt(a,b,r)=IFTE(a==1,b+r,Egypt(IP(a/2), b+b, (FP(a/2)==0.5)*b+r))' DEFINE

[C.Ret]

Pas de doute que cela doit aussi pouvoir fonctionner sur les premiers RPL.

Je trouve cependant que le terme utilisé, à savoir "vieux RPL" est péjoratif. C'est peut-être vrai, à mon grand regret je n'y peux rien, ça ne fait pas plaisir,... mais "vieux" c'est dur quand même !

Je regardais la définition récurrente et l'utilisation de l'argument 'r' et je me demandais si l'on ne pouvait pas faire autrement, voir sans lui.

Traçons l'évaluation de Egypt(9,8,0) :

Code : Tout sélectionner

Egypt(         9,     8,                   0  ) EVAL
   Egypt(      4,   8+8, IFTE(.5~=0,  8+0, 0) )
   Egypt(      4,    16,                8     ) EVAL
      Egypt(   2, 16+16, IFTE( 0==0, 16+8, 8) )
      Egypt(   2,    32,                   8  ) EVAL
        Egypt( 1, 32+32, IFTE( 0==0, 32+8, 8) )
        Egypt( 1,    64,                   8  ) EVAL
           64+8
             72

Comme on le voit, le ‘r’ ne sert qu’à transmettre à chaque appel récursif la (ou les) retenue(s) afin qu’elle(s) s’accumule à la fin de la récurrence (c'est-à-dire lorsque a==1).

Je propose donc de définir la multiplication à l’aide d’une fonction récurrente n’utilisant que deux arguments (les deux facteurs à multiplier) :

Ce qui s’écrivait donc en vieil RPL :

Code : Tout sélectionner

«   -> a b  'IFTE( FP(a/2)>0 , b , 0)+IFTE( a>1 ,EPrdt( IP(a/2),2*b ),0)'  »
'EPrdt' STO

Traçons l'évaluation de EPrdt(9,x) :

Code : Tout sélectionner

EPrdt(         9,       x) EVAL
x+EPrdt(       4,     2*x) EVAL
x+0+EPrdt(     2,   2*2*x) EVAL
x+0+0+EPrdt(   1, 2*2*2*x) EVAL
x+0+0+ 2*2*2*x +0 
 (1 + 2*2*2)*x
           9*x 

D’ailleurs c’est bien ce que l’on obtient : 9 x Eprdt renvoi ‘x+2*(2*(2*x))’ sur ma vieille RPL !


P.S.:
Mais, en fait 'IFTE( FP(a/2)>0 , b , 0)' c'est bien compliqué pour une expression qui en fait effectue 'b*MOD(a,2)'.

D'où une version alternative en vieil RPL :

Code : Tout sélectionner

«   -> a b  'b*MOD(a,2)+IFTE( a>1 ,MPrdt( IP(a/2),2*b ),0)'  »
'MPrdt' STO

Ou en programme :

Code : Tout sélectionner

«   -> a b 
    « b a 2 MOD *
       IF a 1 > THEN a 2 / IP 2 b * MPRDT + END
     »
»   'MPRDT' STO