ALGORITHME DE BEZOUT : TROUVER U, V ET PGCD(A,B) TEL QUE U.A + V.B = PGCD(A,B)
jesusonline
Messages postés
6814
Date d'inscription
dimanche 15 décembre 2002
Statut
Membre
Dernière intervention
13 octobre 2010
-
8 févr. 2004 à 21:56
sylvanox Messages postés 19 Date d'inscription samedi 5 novembre 2005 Statut Membre Dernière intervention 22 mai 2016 - 9 févr. 2009 à 21:10
sylvanox Messages postés 19 Date d'inscription samedi 5 novembre 2005 Statut Membre Dernière intervention 22 mai 2016 - 9 févr. 2009 à 21:10
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/20263-algorithme-de-bezout-trouver-u-v-et-pgcd-a-b-tel-que-u-a-v-b-pgcd-a-b
https://codes-sources.commentcamarche.net/source/20263-algorithme-de-bezout-trouver-u-v-et-pgcd-a-b-tel-que-u-a-v-b-pgcd-a-b
9 févr. 2009 à 21:10
8 juil. 2004 à 02:02
trouver le PGCD de deux nombres revient à trouver le plus grand nombre qui divise à la fois A et B.
Exemple : 63 et 27
PGCD (63, 27) [également noté : 63 ^ 27] = 9
63 = 7 * 9
27 = 3 * 9
Conséquence directe, si on appelle d le PGCD de A et B :
A/d et B/d sont premiers entre eux.
PGCD(A/d , B/d) = 1
Effectivement 3 et 7 sont premier entre eux.
L'algorithme de Bezout permet de trouver deux nombres que l'on appelera U et V qui, pour deux nombres donné A et B, nous permet d'obtenir la relation suivante :
A*U+B*V = PGCD(A, B)
donc
(9).3 * U + (9).7 * V = (9).1 une petite simplification... par 9
L'algo nous donnerait U -2 et V 1
Dans notre cas cet algorithme prendrait en paramètre A et B, ainsi que trois variables (initialisées ou non) pour stocker le résultat de la fonction : les d, U et V de notre exemple.
29 févr. 2004 à 23:36
ca sert a quoi ?
28 févr. 2004 à 22:53
#define SWAP(a,b) ((a)(a) ^ ((b) (b)^ ((a) = (a) ^ (b))))
souvenirs ....
regrets .... ze vzux mon amiga !!!!!!!!!!!!!!!!!!! ouinnnnnnnnnnnnnnnnnnnn
:-)
26 févr. 2004 à 01:56
Que c'est jolie !
J'avais oublié les propriétés du XOR qui justement permettent ça ...
En tout cas, là, plus de problème de dépassement possible...
j'ai testé et c'est effectivement plus rapide ...
Merci ! je m'en souviendrai ... :)
-~=[{ ZeroCool }]=~-
P.S : Vive l'algo !
25 févr. 2004 à 00:02
a=(a xor (b= b xor ( a = a xor b)))
ou si vous preferez :
a = a xor b
b = b xor a
a = a xor b
ou en asm (pour montrer le peu d'instruction processeur necessaires)
xor eax,ebx
xor ebx,eax
xor eax,ebx
le xor est normallement une instruction + rapide qu'une somme ou une difference
ex :
a=3 , b= 7
a a xor b 3 xor 7 = 4
b b xor a 7 xor 4 = 3
a a xor b 4 xor 3 = 7
23 févr. 2004 à 02:04
Pour inverser les valeurs que contiennent deux variables il y a la technique bourrin :
Celle que tout le monde connait : On crée une troisième variable temporaire :
Dim a as integer , b as integer
a = 2
b = 3
Dim tmp as integer
tmp = a
a = b
b = tmp
...
Mais pour des valeurs numériques on peut procéder autrement :
a = a + b
b = a - b
a = a - b
exemple a 3 et b 7 :
a a + b 3 + 7 = 10
b a - b 10 - 7 = 3
a a - b 10 - 3 = 7
On comprend vite que les valeurs de départ sont sauvegardés.
Mais le but de l'algo n'est pas de faire a b et b a
mais :
U = V
V = U - V * (A\B)
J'ai donc adapté...
9 févr. 2004 à 19:08
et ensuite, j'ai bien essayer de comprendre comment il marche ton programme mais pas moyen de comprendre la fin..... tu mets d'abord u= puis v= et ensuite de nouveau u=.... et là je capte plus rien... si tu pourais juste expliquer ca vite fait, ca serait sympa... :-)
8 févr. 2004 à 22:16
8 févr. 2004 à 21:56
Ta source est bien :) pensé et assez simple