Discussion :

[marko1587]

bonjour

pour mon tp, nous devons comparer (nombre de multiplications) trois méthodes d'exponentiation rapide : binaire, facteurs et arbre de puissances de Knuth.
j'ai pu avoir le chemin qui mène du sommet au nœud de valeur 'n', mais j'ai des questions :

- si 'l' désigne la longueur de ladite chaîne, est ce que le nombre de multiplications nécessaires est égal à 'l' ?

- comment utiliser les valeurs de cette chaîne pour calculer la puissance ? par exemple : x^9, la chaîne correspondante : 1, 2, 3, 6, 9

merci

[kamel.bensaid]

• Si "l" désigne le nombre de nœuds depuis la racine de l'arbre de puissance jusqu'au nœud de valeur "n" alors le nombre de multiplications à effectuer est égal à "l - 1"
• Pour utiliser cette méthode, il te faut en plus avoir pour chacune de ces valeurs (nœuds) leurs parents éloignés.
  Dans ton exemple :
  
  • 1 pas de parent
  • 2 = 1 + 1
  • 3 = 2 + 1
  • 6 = 3 + 3
  • 9 = 6 + 3
  
  Cette méthode nécessite la sauvegarde de toutes ces valeurs intermédiaires, cela permet de diminuer le nombre de multiplications nécessaires mais en contre partie il faut beaucoup de calculs et d'espace mémoire pour sauvegarder l'arbre (du moins, jusqu'au nœud qui représente la puissance à calculer) et la chaîne de puissance.

[marko1587]

merci pour la reponse, je commence enfin a comprendre