Travaux Dirigés
Algorithmique et Programmation en C (ANSI)
Exercice 14 – Calcul de puissance rapide
10 juin 2025
Exercice 14 – Calcul de puissance rapide
Objectif
Écrire une fonction qui reçoit comme paramètres un réel x et un
entier n ≥ 0, et retourne xn en utilisant la méthode d’exponentiation
rapide décrite à l’aide des suites (yi ), (pi ) et (zi ) :
– p0 = n, pi+1 = ⌊pi /2⌋
– y0 = x, yi+1 = yi2
– z0 = 1, zi+1 = zi × yi si pi est impair, sinon zi
La suite (pi ) s’annule à partir d’un certain rang, et la valeur zi
correspondante est alors xn .
Algorithme en pseudo-code
Entrée : x réel, n entier ≥ 0
Sortie : xn calculé efficacement
1. z ← 1, y ← x, p ← n
2. Tant que p > 0 faire
– Si p est impair alors z ← z × y
– y ←y×y
– p ← ⌊p/2⌋
1
TD Algorithmique 2
3. Retourner z
Programme C ANSI
1 # include < stdio .h >
2
3 double puissance ( double x , int n ) {
4 double z = 1.0;
5 double y = x ;
6 int p = n ;
7
8 while ( p > 0) {
9 if ( p % 2 == 1) {
10 z *= y ;
11 }
12 y *= y ;
13 p /= 2;
14 }
15
16 return z ;
17 }
18
19 int main () {
20 double x , res ;
21 int n ;
22
23 printf ( " Entrez ␣ un ␣ reel ␣ x ␣ : ␣ " ) ;
24 scanf ( " % lf " , & x ) ;
25
26 printf ( " Entrez ␣ un ␣ entier ␣ n ␣ >= ␣ 0 ␣ : ␣ " ) ;
27 scanf ( " % d " , & n ) ;
28
29 if ( n < 0) {
30 printf ( " Erreur ␣ : ␣ l ’ exposant ␣ doit ␣ etre ␣ >= ␣ 0.\ n ") ;
31 return 1;
32 }
33
34 res = puissance (x , n ) ;
35 printf ( " Resultat ␣ : ␣ %.5 lf ^% d ␣ = ␣ %.5 lf \ n " , x , n , res ) ;
36
37 return 0;
38 }
Listing 1 – Calcul de puissance rapide
TD Algorithmique 3
Exemple d’exécution
Entrez un réel x : 2
Entrez un entier n >= 0 : 10
Résultat : 2.00000^10 = 1024.00000
