La fonction puissance, v2⚓︎
On souhaite améliorer la vitesse de calcul de \(a^n\), pour \(a\) flottant et \(n\) entier naturel.
On constate que
- \(a^{2022} = a^{1011} × a^{1011}\)
- \(a^{2023} = a^{2022} × a\)
et que de manière générale
- si \(n\) est pair, \(a^n = a^{n/2} × a^ {n/2}\), avec \(n/2\) qui est bien entier
- sinon, \(a^n = a^{n-1} × a\)
def puissancepy-undv2(a: float, n: int) -> float:bksl-nl "Renvoie a à la puissance n, pour n >= 0"bksl-nl # méthode récursivebksl-nl ...bksl-nlbksl-nlassert puissancepy-undv2(3.0, 0) == 1.0bksl-nlassert puissancepy-undv2(3.0, 1) == 3.0bksl-nlassert puissancepy-undv2(3.0, 4) == 81.0bksl-nlassert puissancepy-undv2(3.0, 5) == 243.0bksl-nlassert puissancepy-undv2(2.0, 10) == 1024.0bksl-nlbksl-nlbksl-nl
Exercice
Donnez une version récursive de puissance_v2 utilisant ce principe.
Indice
On n'oubliera pas le cas de base n = 0.
Réponse
def puissance_v2(a: float, n: int) -> float:
"Renvoie `a` à la puissance `n`, pour n >= 0"
if n == 0:
# cas de base
return 1.0
elif n % 2 == 0:
# n est pair
y = puissance_v2(a, n // 2)
return y * y
else:
# n est impair
return puissance_v2(a, n - 1) * a
Compléxité
Le cout du calcul de puissance_v2(a, n) est inférieur à deux fois le nombre de bits de n.
Voici un exemple d'arbre d'appels récursifs ← site externe de visualisation.
>>> puissance_v2(3.5, 13)
11827271.778198242
puissance_v2(3.5, 13) = puissance_v2(3.5, 12) × 3.5 = 11827271.778198242
puissance_v2(3.5, 12) = puissance_v2(3.5, 6) au carré = 3379220.5080566406
puissance_v2(3.5, 6) = puissance_v2(3.5, 3) au carré = 1838.265625
puissance_v2(3.5, 3) = puissance_v2(3.5, 2) × 3.5 = 42.875
puissance_v2(3.5, 2) = puissance_v2(3.5, 1) au carré = 12.25
puissance_v2(3.5, 1) = puissance_v2(3.5, 0) × 3.5 = 3.5
puissance_v2(3.5, 0) = (réponse directe) 1.0
On note alors ce cout \(\mathcal O(\log(n))\), ainsi pour tout flottant et tout entier sur 32 bits, il y aura moins de 64 multiplications, ce qui rend cette version bien plus performante que puissance_v1(a, n).