Carrés répétés

par **miboulish** » 04 Oct 2008, 17:41

bonjour, ca fait beaucoup de post pour ce soir mais...
je doit préparer un TP pour lundi... mais pour pouvoir le préparer il me faut comprendre ce qu'est la technique des carrés répétés, qui apparament est trés utile pour calculer la puissance n-ieme d'un nombre.

Alors j'aimerai, si possible qu'on m'exiple en quoi ca consiste, comment ca marche... et un exemple, ca aide beaucoup souvent...

voila voila, merci d'avance...

par **Maxmau** » 04 Oct 2008, 18:28

miboulish a écrit:bonjour, ca fait beaucoup de post pour ce soir mais...
je doit préparer un TP pour lundi... mais pour pouvoir le préparer il me faut comprendre ce qu'est la technique des carrés répétés, qui apparament est trés utile pour calculer la puissance n-ieme d'un nombre.

Alors j'aimerai, si possible qu'on m'exiple en quoi ca consiste, comment ca marche... et un exemple, ca aide beaucoup souvent...

voila voila, merci d'avance...

Bj

Tout entier n sécrit comme somme dentiers puissances de 2. (écriture en base 2)
Ex ; 15 = 2^3 + 2^2 + 2 +1 = 8 + 4 + 2 +1
21 = 2^4 + 2^2 + 1 = 16 + 4 + 1

Pour calculer a^21, on décompose 21 comme ci-dessus et on écrit la suite suivante où chaque entier est le carré du précédent :
a , a² , a^4 , a^8 , a^16
Doù : a^21 = a^16 . a^4 . a produit dentiers de la liste ci-dessus

par **leon1789** » 04 Oct 2008, 18:29

pour calculer x^64, on fait (((((x²)²)²)²)²)² , ce qui fait 6 multiplications !

par **leon1789** » 04 Oct 2008, 18:32

En fait, rigoureusement, il existe deux méthodes d'exponentiation dichotomique : elles reposent toutes les deux sur l'écriture binaire de l'exposant. Mais elles diffèrent dans les puissances intermédiaires calculées.

par **miboulish** » 04 Oct 2008, 18:41

oki... merci !
moi on me demande pour a^45
ca fait donc bien ((((a²)²a)²a)²)²a
mais il nous demande alors " Combien de carrés et de multiplications doit on calculer au au plus en fonction de n avec cette methode...
je crois avoir bien saisie la methode, ici on calcule 5 carré et 3 multiplication... mais je ne saurais pas l'exprimer en fonction de n pour a^n ...
help me please ^^

par **leon1789** » 04 Oct 2008, 18:47

miboulish a écrit:oki... merci !
moi on me demande pour a^45
ca fait donc bien ((((a²)²a)²a)²)²a

oui, impec

miboulish a écrit:mais il nous demande alors " Combien de carrés et de multiplications doit on calculer au au plus en fonction de n avec cette methode...
je crois avoir bien saisie la methode, ici on calcule 5 carré et 3 multiplication... mais je ne saurais pas l'exprimer en fonction de n pour a^n ...
help me please ^^

écris 45 en base 2 : le nombre de "mise au carré" et le nombre de "multiplications" se voient bien sur l'écriture en base 2.
On te laisse deviner ? (prends plusieurs exemples, tu trouveras vite j'imagine, comme n=15 et n=16 )

par **draven** » 04 Oct 2008, 20:04

petit probleme avec le compte miboulish ... alors j'en ai fait un autre.. dsl ..

bon ui en base 2 je trouve:
pour 45 : 101101
pour 15 : 1111
pour 16 : 10000

et donc a^15= ((((a²)a)²a)²a)²a
a^16 = (((((a²)a)²)²)²)²

mais je comprend pas le coups du nombre de multiplication et carré calculé en surtout en fonc de n ...

par **leon1789** » 04 Oct 2008, 20:45

deux coquilles pour a^16 et a^15...

draven a écrit:mais je comprend pas le coups du nombre de multiplication et carré calculé en surtout en fonc de n ...

indication :
il y a des liens entre
-- la longueur du développement binaire de n et le nombre de mises au carré.
-- le nombre de 1 dans le développement binaire de n et le nombre de multiplications

par **moioupas** » 04 Oct 2008, 20:51

apparement lui et moi avons le meme probleme...

je voit bien que le nombre de chiffre de l'ecriture en base 2 est le meme que le nombre de mis au carré, et que le nombre de 1 dans l'ecriture en base 2 est le meme que le nombre de multiplication... mais je ne sais pas le mettre en fonction de n ....

a et si il etait possible aussi de repondre a son post " suite et recurence" ...
j'ai le meme probleme ... :cry:

par **leon1789** » 05 Oct 2008, 13:50

miboulish a écrit:help me please ^^

C'est bon maintenant ??

Carrés répétés

carrés répétés

Qui est en ligne