Puissances d'un nombre
Écrire une fonction python récursive :
| Entrée | Un nombre x non nul et un entier naturel n. |
|---|---|
| Sortie | xn |
On utilisera pour cela la définition :
def puissance(x,n) :
if n == 0 : return 1
else : return x * puissance(x, n-1)
print(puissance(3,4))
ou encore :
def puissance(x, n, p = 1) :
if n == 0 : return p
else : return puissance(x, n-1, p*x )
print(puissance(3,3))
Dans le script donné en corrigé de l'exercice précédent, compter le nombre de multiplications.
Notons \(u_n\) le nombre de multiplications pour le calcul de puissance(x,n). On a \( u_0 = 0\) et \( u_n = 1 + u_{n-1} \). On a donc \(u_n = n \). Complexité linéaire.
Pour améliorer le temps de calcul (par réduction du nombre de multiplications), on utilise un principe de dichotomie.
Notons q le quotient de la division entière de n par 2.
Pour calculer \( x^n \), il suffit donc de calculer \(x^q \) et de faire suivre cela d'une ou deux multiplications.
Écrire une fonction python récursive suivant ce principe :
| Entrée | Un nombre x non nul et un entier naturel n. |
|---|---|
| Sortie | xn |
def puissance(x, n) :
if n == 0 : return 1
if n == 1 : return x
p = puissance(x, n//2)
if (n%2 == 0) : return p*p
else : return p*p*x
print( puissance(3,3) )
ou encore :
def puissance(x, n, p = 1) :
if n == 0 : return p
if (n%2 == 0) : return puissance(x*x, n//2, p )
else : return puissance(x*x, n//2, p*x )
print( puissance(3,3) )Décomposition sur un exemple :
| puissance(3,3) | = | puissance(3,3,1) |
| = | puissance(3*3,1,1*3) | |
| = | puissance((3*3)*(3*3),0,1*3*(3*3)) | |
| = | 1*3*(3*3) |
| puissance(3,4) | = | puissance(3,4,1) |
| = | puissance(3*3,2,1) | |
| = | puissance((3*3)*(3*3),1,1) | |
| = | puissance(((3*3)*(3*3)) * ((3*3)*(3*3)),0,1*((3*3)*(3*3))) | |
| = | 1*((3*3)*(3*3)) |
L'objectif des questions 1 et 2 est de faire comprendre la notion de logarithme (entier) aux élèves.
On observe un changement de valeur à chaque puissance de 2, ce qui amène à la conjecture \( t_n = \lfloor \log_2(n) \rfloor \).
On peut ensuite établir la formule par récurrence : on suppose \( t_j = \lfloor \log_2(j) \rfloor \) pour \( j < n \).
On a alors \( t_n = 1 + t_q = 1 + \lfloor \log_2(q) \rfloor = \lfloor 1 + \log_2(q) \rfloor = \lfloor \log_2(2q)\rfloor
= \lfloor \log_2(2q+1)\rfloor \)
from math import floor, log
def t(n):
if n <= 1 : return 0
return 1+t(n//2)
def tt(n) :
return floor( log(n,2) )
for k in range(1,20):
print(" t({}) = {}. {}".format(k, t(k), t(k) == tt(k)) )
from math import floor, log
def w(n):
if n <= 1 : return 0
return 2+w(n//2)
def ww(n) :
return 2*floor( log(n,2) )
for k in range(1,20):
print(" w({}) = {}. {}".format(k, w(k), w(k) == ww(k)) )
Notons \( v_n \) le nombre de multiplications pour l'appel puissance(x,n).
On a \(v_0 = 0 \), \( v_1 = 0 \), \(v_2 = 1 + v_1 = 1 \), \( v_3 = 2 + v_1 = 2\) .
De façon plus générale, en notant q le quotient de la division de n par 2 :
Avec les questions précédentes, on en déduit que \( \lfloor\log_2(n)\rfloor \leqslant v_n \leqslant 2 \lfloor\log_2(n)\rfloor \).
Comparer sur quelques valeurs de n le nombre de multiplications pour chacun des deux scripts précédents.
Pour bien saisir le gain, rien ne vaut quelques valeurs. Calculons par exemple \(x ^ {1000000} \) :
Et :