Discussion :

[carhelle007]

Salut a tous

J'ai du mal avec mon exo d'algo :/

Donc voici le sujet :
Dans l'antiquite, les egyptiens savaient sans utiliser la multiplication sauf par 2, calculer le produit de deux entiers positifs, par decomposition successives grace a la decomposition suivante

a*b = a+a*(b-1) si b est impair
a*2 * (b/2) sinon
Jusqu'a ce que b=1

Ecrire l'algorithme realisant le produit d de nombres entiers en utilisant cette methode.

Un grand merci a ceux qui vont repondre

[anapurna]

salut

dans mon souvenir la multiplication egyptienne etais
Pour tout nombre N
trouver plus grand diviseur multiple de 2
et refaire l’opération jusqu’à que le reste soit égale a 0

imaginons que tu ai : 251 * 21
on cherche les valeur de 2 pour le plus petit nombre donc dans notre cas 21
la table des puissance de 2 est :
2⁰ = 1
2¹ = 2
2² = 2*2 = 4
2³ = 2*2*2 = 8
....
ce qui nous donne les valeurs suivantes :
1;2;4;8;16;32;64;128 ...

on décompose notre multiplicateur :
21 - 16 = 5
5 - 4 = 1
1 - 1 = 0

21 = 16 + 4 + 1 donc d'après la distributivité de la multiplication par rapport à l'addition, 21 × 251 = (16 + 4 + 1) × 251 = 16 × 251 + 4 × 251 + 1 × 251
= 4016+1004+251= 5271

ce que nous pourrions traduire par

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
x ← a
y ← b
z ← 0
TANSQUE y >= 0 FAIRE
  SI y  IMPAIRE ALORS
     z ← z + x
  FINSI
  x ← 2 × x
  y ← y div 2
FIN FAIRE
résultat z

[stendhal666]

oui c'est bien ça!

La multiplication égyptienne fonctionne en isolant les puissances de 2 qui composent le multiplicateur. Si tu prends une représentation binaire de ton multiplicateur, le principe saute aux yeux:

21 = 10101b
= 10000b
+ 100b
+ 1b

Comme l'ordinateur a une représentation binaire des nombres, cet algorithme est très rapide (pour les nombres entiers positifs):

multiplier par 2 revient à décaler d'un bit vers la gauche (en C: x << 1), par 2² de deux bits, 2³ trois bits, etc.
diviser par 2 revient à décaler d'un bit vers la droite (en C: x >> 1)
enfin on peut tester si le premier bit est allumé avec x & 1

d'où

Code C :

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

1
2
3
4
5
6
7
int mult(int a, int b) {
  if (a == 1) return b;
  if (a & 1)
    return b + mult(a - 1, b);
  else 
    return mult(a >> 1, b << 1);
}

Naturellement on peut améliorer cet algorithme mais le principe reste le même.

NB: l'algorithme s'appelle également la multiplication du paysan russe

[carhelle007]

Merci bcp
La c'est claire

A toute