Bonjour,

Soient x et n deux entiers strictement positifs.
1.Ecrire une fonction exp(x,n) qui calcule naïvement xⁿ sans utiliser la fonction puissance de pyhton.
2.Estimer son cout en multiplication.
3.Justifier la décomposition de l'entier n sous la forme :
n=i[0,p]  a_i 2ⁱ
où les a_i sont des éléments de [0,1] avec a_p =1 . Exprimer p en fonction de n.
4.On pose u₀=n ; v₀=x et w₀ = 1 et pour tout i[0,p-1] :
u_i+1= partie entière de (u_i/2)
v_i+1 =v_i²
w_i+1= v_iw_i  si u_iimpair
=w_i sinon
a) Exprimer u₁, v₁ et w₁ en fonction de x et des (a_i)_i[0,p]).
b)Montrer par récurrence que pour tout k  [0,p] ,
u_k=_i[k,p] a_i2^i-k
v_k=x^{2^k}
w_k=x(^{_i[0,k-1]a_i2^i})
c)Donner alors les valeurs de u_p,u_p+1, w_p+1

Je bloque à partir du moment où il faut exprimer p en fonction de n.
Merci de bien vouloir m'aider.