Puissance rapide — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 4)

Puissance rapide

Méthodes · niveau 3 (difficile)

Énoncé

La méthode puissance du cours effectue $n + 1$ appels pour calculer $x^{n}$ . On remarque que $x^{n} = (x^{n /2})^{2}$ si $n$ est pair et $x^{n} = x \cdot (x^{⌊ n /2 ⌋})^{2}$ si $n$ est impair.

Écrire une méthode récursive static long puissanceRapide(long x, int n) fondée sur cette remarque, qui ne fait qu'un seul appel récursif.
Compter les appels pour $n = 20$ et pour $n = 1000$ , et comparer avec la version du cours.
Un camarade écrit return puissanceRapide(x, n / 2) * puissanceRapide(x, n / 2); dans le cas pair. Le résultat est-il juste ? Qu'a-t-il perdu ?

Corrigé


static long puissanceRapide(long x, int n) {
    if (n == 0) return 1;
    long y = puissanceRapide(x, n / 2);        // UN seul appel récursif
    if (n % 2 == 0) return y * y;
    return x * y * y;
}

Chaque appel divise $n$ par deux : on passe par $20, 10, 5, 2, 1, 0$ , soit $6$ appels contre $21$ pour la version du cours. Pour $n = 1000$ : $11$ appels contre $1001$ . Le nombre d'appels est de l'ordre de $lo g_{2} n$ , au lieu de $n$ . Mesures du programme :


3^20 = 3486784401 (21 appels) = 3486784401 (6 appels)
puissanceRapide(1, 1000) : 11 appels
puissanceNaive(1, 1000) : 1001 appels

La version du camarade donne le bon résultat, mais elle fait deux appels récursifs identiques : le nombre d'appels double à chaque niveau, et l'on retombe sur environ $2 n$ appels. Tout le gain vient de ce que l'on mémorise $x^{n /2}$ dans une variable pour ne le calculer qu'une fois.