Algorithme etendu euclide

[kadaid]

bonjour

Voici un algorithme d'euclide étendu sur Wiki, je l'ai programmé sur ma calculette Nspire mais il ne marche pas!

Exmple a=520, b=148
résultat:(r,u,v) =1 148 0

Entrée : a, b entiers (naturels)
Sortie : r entier (naturel) et u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v

Initialisation : r := a, r' := b, u := 1, v := 0, u' := 0, v' := 1
q quotient entier
rs, us, vs variables de stockage intermédiaires

les égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle

tant que (r' 0) faire
q := r÷r'
rs := r, us := u, vs := v,
r := r', u := u', v := v',
r' := rs - q *r', u' = us - q*u', v' = vs - q*v'
fait
renvoyer (r, u, v)

Merci pour vos commentaires

[sylvainc2]

Ce pseudo-code me semble correct. Tu dois avoir fait une erreur de codage dans ton programme de calculatrice.

[kadaid]

Bonjour Sylvainc2

Ce pseudo-code me semble correct. Tu dois avoir fait une erreur de codage dans ton programme de calculatrice.

Voici mon code sur TI Nspire CX CAS:

Define euclidetendu(a,b)=
Prgm
:Local u,v,r,u1,v1,r1,q,us,vs,rs ( r1=r' car la calculette n'accepte pas les primes)
:©r=pgcd(a,b) et au+bv=r
:r:=a: r1:=b:u:=1: v:=0:u1:=0:v1:=1 ( r1=r' car la calculette n'accepte pas les primes)
:While r1;)0
:q:=((r)/(r1)):rs:=r: us:=u: vs:=v
r:=r1: u:=u1: v:=v1
:r1:=rs-q*r1: u1=us-q*u1: v1=vs-q*v1
:EndWhile
isp {r,u,v}
:EndPrgm

Peut être qu'il y a une erreur que je n'ai pas Vue ? Pourtant j'ai vérifié plusieurs fois.

[sylvainc2]

J'ai recopié ce programme en python et il marche correctement. Cependant, l'instruction q:=((r)/(r1)) doit faire une division entière, mais je pense que la calculatrice fait une division réelle. C'est çà qu'il faut changer (en python je fait une division entiere q=r//r1 et ca donne la bonne réponse pgcd=4, u=2 et v=-7 pour a=520 et b=148. Mais si je fait une division réelle ca donne pgcd=148 u=0 et v=1 comme pour ta réponse).

[mathelot]

faudrait que je recopie un algorithme d'Euclide en base 2 qui a l'air proche de la machine
que j'ai aperçu dans Knuth:

ça commence par
si u et v pairs gcd(u,v)=2 gcd(u/2,v/2)

[kadaid]

Bonjour

Oui il faut une division euclidéenne.

Donc q=int(r/r1).
Mais le reste de cette division qui est:r-r1*q, faut il l'utiliser ou non car maintenant mon résultat est:
pgcd=4, u=0 et v=1

S'il faut l'utiliser, à quelle variable faut il l'attribuer ?

[sylvainc2]

D'après moi ce programme devrait marcher, mais je ne connais pas du tout le langage de programmation de cette calculatrice.

Est-tu sûr que l'instruction

:r1:=rs-q*r1: u1=us-q*u1: v1=vs-q*v1

est correcte? Le symbole d'assignation semble être :=, il manquerait pas un : par hasard?

[kadaid]

Merci Sylvain, c'était bien := et non =, une erreur de frappe que je n'ai pas vue!

[kadaid]

Bonjour
Encore moi,

l'algorithme d'euclide étendu permet de trouver une solution particulière (u0,v0) de l'équation au+bv=pgcd(a,b)

Mai si pgcd(a,b)=1 et le second membre different de 1: 17u+29v=7, comment faire ?

Personnellement je tâtonne avec deux boucles dans [-n;n] pour trouver (u0,v0).

Y a t il une méthode plus efficace que ce qu je fais ?

[sylvainc2]

Si d=pgcd(a,b) et on cherche des solutions à au+bv = c: tu dois déjà savoir qu'il y a des solutions seulement si c est un multiple de d, ou encore si c/d est un entier.

Donc on trouve les solutions à au0 + bv0 = d avec euclide étendu, puis on les multiple par c/d car évidemment: a*(u0*(c/d)) + b*(v0*(c/d)) = d*(c/d) = c.

[zygomatique]

salut

17u + 29v = 7

17(u + v) + 12v = 7

5(u + v) + 12(u + 2v) = 7


une solution évidente est alors :

u + 2v = 1
u + v = -1

...

[alphamethyste]

l'algorithme d'euclide étendu permet de trouver une solution particulière (u0,v0) de l'équation au+bv=pgcd(a,b)

Mais si pgcd(a,b)=1 et le second membre different de 1: 17u+29v=7, comment faire ?

l'algorithme étendu d'Euclide 17x+29y=PGCD(17,29)=1 te permet de trouver x et y

une fois que tu as ton x et ton y tu applique 17x+29y=1 puis tu obtiens z



puis tu pose 7=z.w donc tu obtiens

par consequent

et donc

et donc

[zygomatique]

rien compris ....

une fois trouvé x et y tels que 17x + 29y = 1

alors tout simplement 17(7x) + 29(7y) = 7

...

[alphamethyste]

rien compris ....

une fois trouvé x et y tels que 17x + 29y = 1

alors tout simplement 17(7x) + 29(7y) = 7

...

oui ça marche aussi mais ça la jette moins :lol3:

j'ai regardé les deux premiers épisodes des shadocks hier soir

[alphamethyste]

ainsi

17x+29y=1 avec x=12 et y=-7

avec ta méthode tu trouve 17u+29v=7 avec u=84 et v=-49 deux relatifs

avec ma méthode je trouve 17u+29v=7 avec u=84/85 et v=-49/145 deux rationnels

c'est tout aussi juste même si ça méthode releve de la logique des shadocks

:ptdr: