Défi puissance

par **lulu2468** » 05 Jan 2009, 09:54

Bonjour, j'espère que je poste au bon endroit.

Je suis en train de faire une recherche sur le fait de calculer une puissance à l'aide de multiplications (logique :id: ). Mon objectif est d'utiliser le moins de multiplications possible pour faire mon calcul.
J'ai quelques idées qui ne me paraissent pas très optimisées.

Une idée pour réduire un maximum le nombre de multiplication à faire pour calculer la puissance d'un nombre serait vraiment le bienvenue.

Merci d'avance :)

par **mathelot** » 05 Jan 2009, 10:10

aloha,

içi

par **lulu2468** » 05 Jan 2009, 10:31

Sa répond à ma question, je n'avais pas trouver ce lien ...

Merci de l'aide ;)

par **Doraki** » 05 Jan 2009, 13:00

C'est une bonne méthode générale, mais pour des exposants spécifiques,
il y a souvent des méthodes plus courtes que ça.

Par exemple, on peut calculer n^15 en 5 multiplications (au lieu de 6 pour l'exponentiation rapide) :

On fait ça en calculant n^3 (2 multiplications), puis (n^3)^5 (3 multiplications) avec l'exponentiation rapide.

Et puis même, il y a certains cas où la méthode optimale n'est pas obtenue en factorisant l'exposant et en appliquant l'exponentiation rapide par petits bouts.

A ma connaissance il n'y a pas d'algorithme rapide pour trouver la méthode optimale.

par **mathelot** » 05 Jan 2009, 23:26

re,

qu'est-ce que c'est comme problème ? graphe, combinatoire, récursivité ????

Défi puissance

défi puissance

Qui est en ligne