« Programmation algorithmique/Nombre d'opérations optimal » : différence entre les versions
Contenu supprimé Contenu ajouté
Ligne 37 :
*La valeur de l'exposant p en binaire s'exprime de la façon suivante :
:<math>p = \sum_{i=0}^\infty p_i \times 2^i</math>
*Chaque bit <math>i</math> de p est testé, s'il vaut 1, il faut multiplier le résultat temporaire par <math>n^{2^i}</math>. La relation mathématique entre les puissances est utilisée. Par exemple : <math>n^{2^1} \times n^{2^3} = n^{2^1+2^3}</math>. Donc pour tous les bits de <math>p</math>, on a :
:<math>\begin{matrix} && p_0 \times n^{2^0} \times p_1 \times n^{2^1} \times \cdots\\
=&& n^{p_0 \times 2^0 + p_1 \times 2^1 + \cdots}\\
=&& n^p \end{matrix}</math>
| |||