Exponentiation rapide

Un exemple simple d'exponentiation rapide, basé sur le développement en base deux : expo.c. Le principe mathématique en est exposé paragraphe I.8.1 du cours. Remarquer dans le code comment on travaille directement sur les bits de l'exposant, celui-ci étant naturellement représenté en base 2 en mémoire. N'hésitez pas à dérouler la fonction à la main pour vous convaincre qu'elle traduit bien, de façon itérative, la formule du cours.

Vous êtes invités à mesurer le temps de calcul pour des valeurs de plus en plus grandes de l'exposant (jusqu'à 232...) pour constater qu'il est linéaire en la taille (nombre de bits) de l'exposant. À l'inverse, le temps de calcul de la méthode naïve est exponentiel, et vous serez rapidement obligés de l'abandonner pour pouvoir augmenter l'exposant.

Pas grand-chose à ajouter sur ce programme assez court. Comme d'habitude, la méthode présentée est une des plus simples et des algorithmes plus performants sont présentés dans le volume 2 de The Art of Computer Programming de Knuth.