Narration de recherches sur algorithmes 1S

[Doridoriane]

J'ai une narration de recherches a rendre pour la rentrée sur un algorithme qui permet de calculer a puissance n. Le voici:
Entrée : Saisir un nombre A
Saisir un nombre entier positif N
Initialisation : Variable R
Affecter a R la valeur 1
Traitement: Tant que N>0
Si N est pair
Alors
Affecter a A la valeur A*A
Affecter a N la valeur N/2
Sinon
Affecter a R la valeur R*A
Affecter a N la valeur N-1
Fin Si
Sortie: Afficher la valeur R.
J'ai deja repondu a un parte ou il etait question de savoir combien de multiplications sont faites pour 5 puissance 4, 4puissance 5, 300 puissance 64 et 64 puissance 300.
Je suis maintenant bloquée pour les questions suivantes:
- Comment peut on utiliser cet algorithme pour calculer 2 puissance -5 ?
- Cet algorithme se termine-t-il toujours?
- Comment etre sur que l'algorithme calcule bien a puissance n ?
- Est ce que l'algorithme proposé est + rapide que l'usuel, càd est ce que l'algorithme permet d'obtenir une puissance avec moins de calculs ? peut on trouver un algorithme qui fasse mieux ?
Merci d'avance

[paquito]

Il manque fin tant que; sinon l'algorithme fonctionne très bien! Pour calculer 2^10, il fait 5 multiplications, mais il faudrait tenir compte du temps mis par le programme. Fait un essai avec A=2 N=7 par exemple pour comprendre son fonctionnement; pour calculer 2^-5, il suffit de calculer (1/2)^5, donc pas de problème; J'ai comparé avec un programme basique (n multiplications); le tiens est bien plus rapide par exemple pour N=100 et A=2; est ce le plus rapide? Il y a tellement d'algorithmes que je ne peux pas te répondre. Sinon, l'algorithme s'arrête toujours si N >=0, car les suites N/2 et N-1 sont strictement décroissantes et il fonctionne car il a été conçu pour!

[Doridoriane]

J'ai bien trouvé la réponse avec 2^-5 en calculant (1/2)^5. J'ai également essayer l'algorithme avec 2^100 et cet algorithme est rapide. Je voudrais savoir si il y a un moyen de prouver que les suite N/2 et N-1 sont strictements négatives ?

[paquito]

Pas strictement négatives, strictement décroissantes et dans N toute suite strictement décroissante atteint forcément 0. On a soit U(n+1)-Un =-n/2=<-1 si n est pair, soit u(n+1)-Un=-1 si n est impair; elle va forcément atteindre 0, ce qui stoppe le programme. Si u1=N, ça ne peut pas prendre plus de N étapes.

Le principe de l'algorithme est d'utiliser un maximum de carrés; par exemple:

2^10=(2^2)^5 (A prend la valeur 2^2 et R reste à 1),
(2^2)^5=(2^2)^1(2^2)^4 (R prend la valeur 1xA=(2^2) et A reste à (2^2)),
(2^2)(2^2)^4=(2^2)(2^4)^2 (R reste à (2^2) et A passe à (2^4)),
(2^2)(2^4)^2=(2^2)(2^8)^1 ( R reste à 2^2, A passe à 2^8 et N=1)
donc il reste à effectuer le produit RA=(2^2)(2^8)=(2^10) et à l'afficher!
En tout cela fait 5 multiplications.

[Doridoriane]

J'ai bien compris le principe avec l'exemple que vous avez donné, merci d'ailleurs. Est-ce que le fait que l'on fasse des élévations successives au carré peut prouver que l'algorithme calcule bien a^n ?

[paquito]

Si tu suis bien l'exemple, tu peut le refaire avec A^10; normalement, tu comprendras pourquoi ça marche; pour 2^100, la démarche qui justifie l'algorithme est:

2^100=(2^2)^50=(2^4)^25=(2^4)(2^4)^24=(2^4)(2^8)^12=(2^4)(2^16)^6=
(2^4)(2^32)^3=(2^4)(2^32)(2^32)^2=(2^36)(2^32)^2=(2^36)(2^64)=2^100.

9 multiplications seulement!
De toutes façons l'algorithme est venu de cette décomposition; il est pas arrivé comme ça! Donc pour le comprendre il faut prendre un exemple simple et suivre toutes les étapes. Tu ne peux pas comprendre un algorithme directement. (Sauf cas très simples).