Discussion :

[Évariste Galois]

Bonjour,

Si je dois calculer a^{17} (a étant un réel) j'ai plusieurs possibilités :

Dans tous les cas je déclare une variable en plus,b.

1)

Code :

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

1
2
 
b = a * a * a * a * ... (17 fois)

2)
(d est une variable entière)

Code :

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

1
2
3
4
5
6
7
8
9
 
b = 1
d = 1
 
faire tant que d < 17
{
   b = (b * a)
   d = d + 1
}

3)
(d est une variable entière)

Code :

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

1
2
3
4
5
6
7
8
9
10
 
b = a
d = 0
 
faire tant que d < 4
{
   a = a * a
   d = d + 1
}
a = a * b

La solution utilisant le moins possible de mutliplication est la solution n° 3.
Dois-je donc en déduire qu'il s'agit de l'algorithme le plus "efficace" ? (je n'ai encore jamais reçu de définition précise de l'efficacité d'un algorithme mais bon ...)

merci

[Matthieu Brucher]

C'est la troisième méthode qui la meilleure.
En fait, 17, c'est 0b10001, donc tu multiplies a par a^16 construit par des carrés successifs.

[Jedai]

Ce problème est celui du calcul de x^n, autrement dit des chaînes additives. Les méthodes pour les résoudre sont la chaîne chinoise ( qui utilise le fait que x^2m = x^m * x^m et x^(2m + 1) = x * x^m * x^m ), la méthode des facteurs (où l'on divise toujours par le plus petit facteur premier) et l'arbre de Knuth. La chaîne chinoise bien que non optimale (on ne connaît pas d'algorithme optimal de toute façon) est excellente et très facile à coder de façon récursive (il y a moyen de la traduire de façon itérative).

--
Jedaï

[Évariste Galois]

Ah bon.
Miles, qu'entend tu exactement par 'la meilleur' ? La plus rapide ?

Excusez moi mais mes connaissances en algo. sont encore assez restreintes ...

[Jedai]

Globalement, le but est d'arriver au résultat avec le moins d'opérations possible (donc le plus rapidement possible), quoi d'autre ? (Encore qu'il faille parfois prendre en compte la consommation de mémoire, mais dans ton cas c'est insignifiant)

Généralement, on définit plutôt un algorithme généraliste, pas aussi spécialisé que ton exemple où on ne peut mettre qu'à la puissance 17, dans ce cas on définit la complexité par rapport à la taille de l'entrée. Je te conseille de lire quelques tutoriels d'algorithmique au plus vite si tu as encore des problèmes avec la notion de complexité (d'efficacité) d'un algorithme : c'est vraiment la base.

--
Jedaï

[Évariste Galois]

Il y a un chapitre entier consacré à la complexité des algorithmes dans mon cours de programmation (il sera vu au cours d'ici quelques temps)
D'autre part ce cours de programmation est suivi d'un cours d'algorithmique plus approfondi au second quadrimestre, donc ça va venir ...

merci