Discussion :

[Stéphane le calme]

Un Docteur décrit un procédé utilisé par un shaman pour faire une multiplication,
peut-il être considéré comme un algorithme mathématique ?

« Engines of Our Ingenuity » est une émission radio régulièrement diffusée sur la National Public Radio (USA). Mise en scène et présentée par le Docteur John Lienhard de l'Université de Houston assisté par d'autres collègues, l'émission espère raconter la naissance et l'évolution de la culture dans la créativité humaine.

Dans son épisode 504 intitulé « Ethiopian binary math », un fermier de l'Ethiopie des années 1940 est confronté à un problème d'arithmétique : il doit vendre 34 chèvres à raison de 7 dollars l'unité. Le problème ? La multiplication est, à cette époque, inconnue dans le village. D'un pas résolu, il se décide à aller voir le chaman, le « sage » du village pour lui demander de fixer un prix de vente équitable pour l'ensemble du troupeau.

Le « sage » a alors creusé deux rangées de petits trous dans la terre. Dans la rangée de gauche, il a rempli le premier trou de 34 cailloux qui représentent chacune des 34 chèvres. Dans le suivant il en met la moitié (ou 17), dans le suivant il en met la moitié (ou 8) et il répète l'opération jusqu'à ce qu'il ne reste plus qu'un seul caillou dans le sixième trou.

Par la suite il se rend sur l'autre rangée et dans le premier trou il dépose 7 cailloux représentatifs de la valeur d'une chèvre. Il en met le double (ou 14) dans le prochain et il continue l'opération jusqu'au sixième trou où il obtient 224 cailloux.

Pour trouver une réponse à apporter au fermier, voici le procédé qu'il a utilisé. Il considère une rangée de pierres comme un couple ; si le premier nombre est pair, il ramène la valeur de la rangée à 0, à contrario si il est impair, il garde la valeur du second nombre. Voici ce qu'il obtient :

• première rangée (34 , 7) premier nombre pair, valeur 0 ;
  
• seconde rangée (17 , 14) premier nombre impair, valeur 14 ;
  
• troisième rangée (8 , 28) premier nombre pair, valeur 0 ;
  
• quatrième rangée (4, 56) premier nombre pair, valeur 0 ;
  
• cinquième rangée (2, 112) premier nombre pair, valeur 0 ;
  
• sixième rangée (1, 224) premier nombre impair, valeur 224.

Par la suite il n'a plus qu'à additionner les valeurs des rangées soit 0 + 14 + 0 + 0 + 0 + 224 ce qui lui donne un résultat de 238 qui correspond au nombre que nous aurions obtenu en faisant l'opération 34 x 7.

Source : Engines of Our Ingenuity (audio)

Et vous ?

Son procédé est-il vérifié ? Aurions-nous obtenu un résultat différent avec d'autres nombres ?

Pouvez-vous expliquer ce procédé ?

Peut-on considérer sa méthode comme un algorithme ?

[Uranne-jimmy]

C'est peut être une réflexion bête hein, mais si il est capable d'en mettre le double ou la moitié, il peut pas simplement comprendre le principe de division et multiplication ? étaler 34 trou et mettre dans chaque trou le prix d'une bête ?

[tontonnux]

... étaler 34 trou et mettre dans chaque trou le prix d'une bête ?

Complètement, mais ça ferait pas assez savant.

[Juda-Priest]

Hmmm... La multiplication n'est qu'un raccourci pour une grande addition d'un même chiffre (ou nombre).

Il arrive à additionner 14 + 224, donc la méthode de Uranne-jimmy aurait du la plus que probable pour une première approche.

C'est peut être une réflexion bête hein, mais si il est capable d'en mettre le double ou la moitié, il peut pas simplement comprendre le principe de division et multiplication ? étaler 34 trou et mettre dans chaque trou le prix d'une bête ?

Bon même si je suis septique, l'approche reste ingénieuse, et tant que Shaman, j'aurais moi aussi utiliser des méthodes tordus pour que ses péons ne puissent pas se passer de moi o/

[ze@rnal]

Et s'il y a 33 ou 35 chèvres la méthode ne marche pas.

Ce n'est donc pas un algorithme, ou alors il est incomplet.

[plegat]

Et s'il y a 33 ou 35 chèvres la méthode ne marche pas.

Ben si, ça marche aussi avec 33 chèvres... et même avec 35... et heureusement d'ailleurs!

33/7/7-16/14/0-8/28/0-4/56/0-2/112/0-1/224/224, ça fait 7+224=231, soit 33*7

Son procédé est-il vérifié ? Aurions-nous obtenu un résultat différent avec d'autres nombres ?

Le procédé se base sur le fait que tout nombre peut s'écrire sous la forme 2*n+k, et sur l'associativité de la multiplication qui dit que (2*a)*b=a*(2*b)

Pouvez-vous expliquer ce procédé ?

Ouaip:

On a un nombre X1=2*n1+k1, que l'on veut multiplier par Y1
Si X1 est pair, k1=0, on passe au step suivant
Si X1 est impair, on a k1=1. On met k1*Y1 de côté et on passe au step suivant
Le step suivant revient à calculer ce qu'il reste, soit (2*n1)*Y1... autrement dit n1*(2*Y1), écrit autrement X2*Y2... tiens, ça ressemble à notre expression du début, y'a qu'à itérer!
Au final, on additionne tous les ki*Yi non nuls pour avoir le total.

Peut-on considérer sa méthode comme un algorithme ?

D'après wikipedia:

Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre un problème.

Je crois que la réponse est oui, non?
D'ailleurs c'est la façon de réfléchir d'un ordinateur, quand on décompose les nombres en binaire (appliquer l'algo avec 7*1: 7 ce n'est jamais qu'un tas avec un caillou, un tas avec deux cailloux, et un tas avec 4 cailloux...)

Voir aussi ça pour ceux qui n'ont pas l'audio.

Après, c'est pas parce que le chaman sait compter et que le fermier ne sait pas que c'est forcément de la magie!

[klhoste]

Tiens, ça aurait plu à mon prof d'algèbre tout ça...
ze@rnal: ça fonctionne pour 33 (7 + 224) et 35 (7 + 14 + 224)

[souviron34]

Et si avant l'homme utilisait déjà des algorithmes mathématiques ?
Peut-on considérer sa méthode comme un algorithme ?

Euh... En quoi est-ce une grande nouvelle ????

Depuis l'Antiquité ça existe...

Académie de Paris : Tableur en 3eme : La légende de l'échiquier

D'après ceci, en 620 après JC.

Mais les Contes des Milles Et Une Nuits le mentionne également, des histoires chinoises aussi, de même que les Mayas, l'architecture des pyramides, la construction de la porte d'entrée de Babylone, etc....

Les ingénieurs chinois d'avant JC calculaient et faisaient des digues.
Les Romains faisaient des acqueducs sur plus de 400 km (le Pont du Gard, ou celui de la plaine du Pô)

Eratosthène, en -300, calcule le rayon de la Terre.

Et toute L'histoire de l'astronomie est là pour prouver que depuis au moins 8000 ans, on sait faire des mathématiques...

C'est quoi ce truc ??


Bien sûr que les mathématiques, les algorithmes, et de manière générale le raisonnement mathématique existe depuis des lustres, dans toutes les civilisations...

[Sirus64]

Oui c'est un algorithme !

L'algorithme fonctionne, je l'ai codé sur jsfiddle : http://jsfiddle.net/64uqz/1/ . Pour la preuve voir le commentaire de plegat !

[FrankieSong]

le chaman considère l'ensemble des 34 chèvres à vendre
le prix total à percevoir par le fellah dépend du prix
qu'il va fixer pour une chèvre...

---o---o---o---o---o---o---o---o---o---parenthèse

Je reconstitue "un peu" le contexte "de l'époque":

( c'est normal, de pas savoir compter à cette époque, et c'est normal de s'adresser au chaman
( dans les temps anciens, les "sciences" n'existent pas sans l'homme
( les maths la philo, les savoir-faire sont liés et reposent dans l'esprit d'un homme
( qui est encore assez grand pour contenir tout ce qui est possible de savoir de son époque.
( il est assez bien nourrit pour être délivré du stress de chercher sa pitance lui-même
( il est en capacité d'avoir observé autre chose que le monde pour (sur)vivre.
( le chaman est en retrait, et cela lui donne une position d'abstraction humaine:
( et son esprit --entier dans son corps sans carence-- sans se torturer va reproduire
( la capacité d'abstraction dans des schémas nouveaux, voire des algorithmes...
( le chaman est utile, mentalement, philosophiquement, et astucieusement aux autres
( de la tribus : plus dur encore: il a l'obligation d'être utile par tout les moyens autres:
( moyens autres, car tous les autres sont dans la nécessité de la survivance et la lutte.
( Lui est à suffisance et intellectuellement il est vivant comme les autres chamans,
( qui se considèrent comme des hommes vrais --ainsi que les busch men d'Australie--
( avec leur conception des profondeurs du temps vécu des humains, qu'ils nomment
( "le temps du rêve" --
( Le chaman voit la profondeur --y compris celle de l'ennui des hommes-- les hommes ordinaires
( voient "seulement l'instant présent" et ne sondent pas la "profondeur" du Chaman...

---o---o---o---o---o---o---o---o---fin de parenthèse

Le chaman va avec son recul: être comptable comme cela:
34 chèvres un prix 7
il utilise la table de multiplication par deux
pour calculer l'entier de ( N / 2 )
jusqu'à 1
34 / 2 = 17 Pair 0 on prendra pas le produit
17 / 2 = 8 (8*2+1) Impair 1 prendre le produit
8 / 2 = 4 Pair 0 on prendra pas le produit
4 / 2 = 2 Pair 0 on prendra pas le produit
2 / 2 = 1 Impair 1 prendre le produit

en parallèle à la colonne de division par 2
le chaman fait le produit par deux du prix (et) par --le niveau binaire--

34 1x7 7 laisser
17 2x7 14 à prendre... dans l'addition + 14
8 4x7 28 laisser
4 8x7 56 laisser
2 16x7 112 laisser
1 32x7 224 à prendre... dans l'addition + 224
-------------------------------------
Total des rangs impairs = 238

Effectivement 34 x 7 = 238, mais ce n'est pas le plus important.

Il faut voir -- avec les yeux de notre époque -- que la division
par deux est le procédé qui permet de décomposer tout nombre en
la suite de sous valeurs demi-entières paires ou impaires
et qu'en filigrane les puissances de 2 apparaissent

2^0 = 1 rang 0
2^1 = 2 rang 1
...
ici jusqu'au rang 6 2^6=32 rang 6

les rang binaires qui passent à 1 sont les rangs impairs
on écrirait aujourd'hui : en les lisant de bas en haut

1 0 0 0 1 0 soit

(0*1) + (1*2) + (0*4) + (0*8) + (0*16) + (1*32)
0 + 2 + 0 + 0 + 0 + 32 = 34 (unité chèvres)


( Le chaman fait du binaire sans le savoir
( --au mieux il pressent l'existence de la décomposition binaire d'un nombre--
( sans avoir de preuve pour lui-même que celle-ci est unique et propre à chaque nombre...


Le prix comptabilisé est le bon car il calcule
( 34 x 7 ) + ( 2 x 7 ) = ( 34 + 2 ) * 7
ce qui est en maths actuels l'associativité de la multiplication par rapport à l'addition.


Le procédé est bel et bien un algorithme: ***
il fonctionne quel que soit le nombre d'objets
considérés comme unité (ici chèvre) et l'autre facteur (prix) qui est rendu
additif par l'association opératoire avec les rangs binaires
(0,1)<==>(non, oui)<==>(non ajouté, ajouté)
la table de multiplication par 2 correspond à l'application de l'axiome du choix.
Choix représenté par les deux symboles binaires (n'existe pas/existe)<-->(0,1),
et la table de multiplication opère l'axiome celui du tiers exclu qui sous-tend et démontre le caractère unique de la décomposition binaire d'un nombre.


Le Chaman à raison d’être juste et bon comptable;
aussi le fellah à la chance et le respect de s'adresser à un sage.


*** Nous devons respecter l'effort des anciens et ne pas juger trop vite leur niveau de connaissance, justement en classant leur procédés par niveaux, ni leur attribuer des notes de mérite...

qui à dit : "Et s'il y a 33 ou 35 chèvres la méthode ne marche pas.
Ce n'est donc pas un algorithme, ou alors il est incomplet."

est superficiel et n'a pas approfondi : son regard.

Le fait que le Chaman trace au sol est simple et suffisant pour une affaire terrestre.
Il aura fréquenté des abstractions plus fortes et subtiles qu'il aura consignées plus artistiquement sur des tablettes d'argile (terre+eau)+cuisson par le feu
pour constituer une brique de savoir plus solide et propre à résister au temps... Sinon ne l'aura pas fait cuire et laissé comme tablette de terre crue... dont peu nous sont parvenues au travers des âges. Dommage.

qui à dit : Bon même si je suis septique, l'approche reste ingénieuse,
et tant que chaman, j'aurais moi aussi utilisé des méthodes
tordues pour que mes péons ne puissent pas se passer de moi.

se trompe d'époque et n'est pas bien complaisant avec lui-même.

Le péon est le mot qui désigne l'ouvrier et la subordination au patron
ou au contremaître dans le monde industriel des années 1850 - 1950 en Angleterre.
Ici, il n'y à pas de lien de subordination, mais un respect mutuel, le fellah apporte et paye en nature avec ce qu'il sait extraire avec ses forces de la nature, en contrepartie de l'apport immatériel que lui procure le Chaman.
Le Chaman reste silencieux et ne dit rien que le résultat utile,
sans forfanterie ni artifice technique, ni oratoire prétentieux.
Il reste au sol et montre tout : l'initié comprendra et suivra...
Les autres se contenterons du résultat... et seront très content à défaut d'être comptant.
Le Chaman donne un leçon de simplicité et d'humilité. Le fellah n'achète rien.
Son besoin de sécuriser sa vente dépend du respect qu'il porte au chaman.
Le fellah n'est pas un ouvrier (péon), c'est déjà un chef d'entreprise.
Pas indépendant, mais un entrepreneur malgré tout.

La méthode est tout sauf tordue.
Elle est belle, mathématiquement belle. merci!

[souviron34]

l
La méthode est tout sauf tordue.
Elle est belle, mathématiquement belle. merci!

Je t'ai mis un +1, ce qui de ma part est rare dans cette section

C'est comme les bouliers, et toutes les techniques "d'avant"..

Et en fait, ce qui m'épate - et me désespère - le plus, c'est cette condescendance par rapport à ce qui se faisait avant, et cette croyance d'être "supérieurs" à cause d'une technique ou d'une technologie...


Les chamans, qu'ils soient Africains, Aborigènes d'Australie, Sibériens, Amérindiens, Indiens, Chnois, ou de n'importe où, ont une énorme connaissance, souvent complémentaire mais pas que, des sciences et techniques occidentales..

Mais, au delà des chamans, l'espèce de mépris envers les connaissances d'avant, alors que la majorité des éleveurs d'il y a 200 ans étairtn plus doués en calcul que la majeure partie des éudiants d'aujourd'hui, me laisse perplexe et parfois pessimiste sur l"volution d'une société qui ne réconnait pas l"héritage colossal et la connaissance accumulée par des générations ne disposant pas des outils actuels...

Les architectes de Notre-Dame, du Pont Du Gard, du Colisée, des Pyramides Egyptiennes, du Macchu Picchu, étaient certainement bien meilleurs que ceux 'aujourd"hui, leurs constructions tiennent depuis plus de mille ans..Donc leurs calculs étaient vraiment pas mauvais, hein ?

[Johnny P.]

Oui bon derrière le mot algorithme se cache "réfléchir" et ça existe depuis l'existence de l'intelligence , mais on réfléchit pas de la même manière pour un algorithme informatique qu'un algorithme mathématique.

Même en cuisine on peut dire qu'on fait des algorithmes donc inventer des histoires/mots pour dire la même chose que le mot -> réfléchir ha les humais .

[FrankieSong]

Je vais philosopher malgré le contexte technique, et malgré être sur développez.net, mais il faut des "guides" voire quelques "principes de fond" pour ne pas se perdre dans l'immensité que les hommes découvrent et forment comme connaissances...


Souviron34,
dit, qu'au delà des chamans, il existe une espèce de mépris envers les connaissances d'avant. Que la majorité des éleveurs d'il y a 200 ans étaient plus doués en calcul que la majeure partie des étudiants d'aujourd'hui.
Cela laisse perplexe et parfois pessimiste sur l'évolution d'une société qui ne reconnaît pas l'héritage colossal et la connaissance accumulée par des générations ne disposant pas des outils actuels...



Je lui dirais bien que:

C'est naturel de ne pas se rendre compte des efforts des anciens et des passerelles qu'ils nous ont offertes : Comment imaginer en passant un défilé creusé par les eaux --après que les eaux se soient retirées-- les volumes de terre et de roche qui ont été arrachés. Si le passant au sortir du défilé se retourne et se laisse gagner par le vertige du "bloc" absent...il peut réaliser que le défilé lui-même par sa vacuité est le moyen qui lui est offert pour "passage-court-et-meilleur-que-passer-par-dessus-la-montagne".


C'est le vide qui souvent est/fait l'utilité d'un outil : "enlève" le vide d'une casserole, d'un escalier, d'un sceau , d'un puit!...etc)--- enlève la profondeur au temps ! Aie !

Au passant, il lui faut faire un demi-tour, et quelques instants considérer le vide qu'il vient de franchir. Or, l'esprit du voyageur est absorbé par --considération sur lui-même/les autres de sa famille, sa TRIBUS : pression sociale et nécessité du trajet le poussent et lui interdisent autant un arrêt qu'un retour sur lui-même...Alors un retour sur les autres -- anciens, aussi absent que le défilé est vide -- est impossible.


C'est aussi pour cela que l'entreprise d'un web thématique et sémantique est une entreprise EXTRÊME -- car met en jeu la faculté des concepteurs d'outils d'agrégation de connaissances à rude épreuve ::: car ils doivent écrire les outils de consolidation du WEB sémantique en même temps que garder la profondeur de vue que permettent les raccourcis fournis par les anciens...

Il ne faut pas oublier que notre support d'écriture, n'est pas du papyrus, ni des tablettes d'argile, mais des impulsions électromagnétiques sur des disques en milar tournant à xxx tour/min ::: La vitesse de transfert des données n'est pas le tenons de l'ouvrage, mais le moyen.

L'idée du partage des savoirs anciens & nouveaux, est le chemin; le but serait de faciliter de nouvelles rencontres: coalescences entre les savoirs : au moins ces trois-là : coalescence des savoirs-technique, des savoirs-faire, et des faire-savoirs... Si possible en se respectant par la sincérité de bons échanges, avec savoir-être. Rester joyeux quoi! Courageux & joyeux...


Si nous perdons de vue la profondeur du temps, l'entreprise va à sa perte, et se transformera en Tour de Babel électrique et dangereuse. Il nous faut avoir une pensée --VRAIE -- à l'égard des anciens. C'est cela qui nous donne à voir la profondeur de leurs tâches comme la hauteur de la nôtre qui nous reste à élever... là le Véritable Vertige nous tiens : je sais ma distance aux Anciens et je sais qu'en tant qu'hommes NOUS pouvons avancer d'autant...


Vertige double : au milieu nous sommes d'autant plus "partagés et tranchés" que nous accédons à lire leurs mots et savons combien il nous faudra en "aligner" pour parler à ceux que nous seront dans une époque...à même distance...comme ils rirons de nous aussi pourtant!... Ici cela devient presque trivial : nous pensons avec et à eux --nos anciens-- comme une aiguille d'horloge nous donne l'heure par un mouvement sur un cadran // ici ::: nos pensées respectueuses de leur ARTS doivent se positionner sur les degrés de profondeur et la sincérité de leur sagesse...

Ai-je remis de l'ordre dans le chaos du temps?!
J'espère. Merci.

je résume:

Maths et la Philo ont une surface commune : Logique et volonté de vrai.
Si tu ne t'aides pas d'une pensée, la sagesse du ciel des Anciens te fuit.

[mounaim198]

C'est une technique existante depuis l'antiquité, qui s'appelle Technique de multiplication à la russe, qui est une variante d'une ancienne technique égyptienne, pour plus d'infos voir ici :

[Tryph]

c'est une chouette histoire et ça a permis de multiples reflexions interessantes de la part de ceux qui ont commenté...
mais, pour ma part, j'ai l'impression que c'est juste la scénarisation d'une "curiosité" mathématique, peut être dans le but de la rendre plus interessante aux yeux de ceux qui sont pas forcément attirés par les maths.

pourquoi je pense ça?
bah le shaman dépose 7 cailloux dans le premier trou, 14 dans le second, 28 dans le troisième, etc...
bref, ça nous fait un total de 441 cailloux juste pour la deuxième colonne, plus 66 pour la première colonne...
en fait j'ai du mal à croire que le shaman a toujours sa brouette de cailloux a proximité pour faire ses calculs, d'autant que pour faire un trou assez grand pour mettre 224 de ces cailloux, il lui faudra probablement une bonne pelle (alors que l'article parle juste de petits trous)

et puis faut les compter les tas de cailloux, sans se tromper de préférence...
quite à se prendre la tête à compter des tas de cailloux, ça me parait quand même vachement plus simple de faire 34 tas de 7 cailloux et de compter le total à la fin...

[DonQuiche]

34 chèvres dans le pré, 34 chèvres...
Si j'en vends une à 7 dollars, si j'en vends une...

33 chèvres dans le pré, 33 chèvres...

[fab256]

L’intérêt de l’algorithme est qu’il utilise des opérations binaires simples; le double d'un nombre équivaut a un décalage - shift binaire vers la gauche, la moitié équivaut à un décalage-shift vers la droite, nombre pair/impair équivaut a voir le premier bit ou simplement appliquer un AND 1;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
function multiplication (a, b) {
c = 0;
    while (a>0) {
        if (a & 1) c += b;
        a = a >> 1;
        b = b << 1;
}
return c;
}

vous pouvez tester le code ici : http://jsfiddle.net/ZmCcy/
(voir résultat dans console)

[Sirus64]

Arf c'est pas beau les boucles pour rien. Voici la version récursive terminale :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
function algo_rec(a, b, res) {
    if (a === 1) return b + res;
    var tmp = ~~ (a / 2);
    if (a % 2 === 1) res += b;
    return algo_rec(tmp, b * 2, res);
}

Pour tester : http://jsfiddle.net/64uqz/1/

[pseudocode]

Un Docteur décrit un procédé utilisé par un shaman pour faire une multiplication

A mon sens, il a surtout décrit un procédé pour faire un changement de base par division successive...

34/2 = 17 reste 0
17/2 = 8 reste 1
8/2 = 4 reste 0
4/2 = 2 reste 0
2/2 = 1 reste 0
1/2 = 0 reste 1
--> 34 en binaire (LSB first) = 010001

D'où 34 * 7 = (010001)b * 7 = (0+2+0+0+0+2^5) * 7

Ca fonctionne avec n'importe quels nombres dans n'importe quelle base. C'est juste plus simple/pratique a faire manuellement en base 2.

[knuth33]

C'est juste l'algorithme d'exponentiation rapide (http://fr.wikipedia.org/wiki/Exponentiation_rapide) adapté à la multiplication : on a remplacé les opérations "mise au carré" par "doublement", et multiplication par addition.
Rien de nouveau dans le monde de l'algorithmique, mais quand même très ingénieux de la part d'un shaman perdu au fin fond de l'Ethiopie (si toutefois l'histoire est vraie )