Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

Exponentiation binaire

Posté par
nirosane
28-02-18 à 13:45

Bonjour,

Soient x et n deux entiers strictement positifs.
1.Ecrire une fonction exp(x,n) qui calcule naïvement xn 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]  ai 2i
où les ai sont des éléments de [0,1] avec ap =1 . Exprimer p en fonction de n.
4.On pose u0=n ; v0=x et w0 = 1 et pour tout i[0,p-1] :
ui+1= partie entière de (ui/2)
vi+1 =vi2
wi+1= viwi  si uiimpair
=wi sinon
a) Exprimer u1, v1 et w1 en fonction de x et des (ai)i[0,p]).
b)Montrer par récurrence que pour tout k  [0,p] ,
uk=i[k,p] ai2i-k
vk=x2^k
wk=x(i[0,k-1]ai2^i)
c)Donner alors les valeurs de up,up+1, wp+1

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

Posté par
luzak
re : Exponentiation binaire 28-02-18 à 14:42

Bonjour !
Encadre n entre deux puissances de 2 et tu auras une relation entre n et p.

Posté par
nirosane
re : Exponentiation binaire 28-02-18 à 22:01

D accord merci beaucoup, et pour la question 4-a) je ne vois pas comment les exprimer en fonction de x

Posté par
luzak
re : Exponentiation binaire 01-03-18 à 08:23

Tu traduis simplement tes formules de récurrence :
u_0=n,\;u_1=E(u_0/2) : il suffit donc de diviser n par 2 en cherchant les chiffres binaires de E(n/2) et tu auras u_1.
v_1=(v_0)^2=x^2
n impair se traduit par une propriété simple des chiffres binaires (les a_k) et selon la condition obtenue w_1=v_0w_0=x*1 ou w_1=w_0=1

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !