Algorithmes de recherche de plus grands dénominateurs communs - Page 1

Hier notre ami squale92 m'a demandé si je ne connaissais pas un algo de recherche de PGCD.

Et je n'ai pas pu m'empêcher d'en chercher un par moi-même (c'est tellement tripant l'algorithmie )

Après un algo des plus lents, j'ai décidé de faire mieux, et j'ai testé au hazard divers suites d'opérations... pour tomber sur une suite de calculs (un algorithme quoi) qui semble marcher à tous les coups.

Mais voilà, j'ai donc découvert cet algo totalement par hazard (et beaucoup par chance ) et je ne comprend absolument pas comment il marche !!!

Question du topic : pouvez-vous poster ici tous les algos de recherche de PGCD que vous connaissez, que je compare, si j'ai fait une découverte révolutionnaire
(j'vais l'faire breveter j'aurais des thunes )

Merci

au final, grace à Kevin qui m'a dit "Alogorithme d'Euclide", j'en ai trouvé un sur le net.
(MERCI KEVIN)

Ce matin, en arrivant à l'IUT, je suis passé pr un con qd g dit que j'avais du chercher sur le net
(ben quoi, g po fait spé maths)

C quoi, thibaut, cet algo révolutionnaire que tu as découvert et dont tu ne comprends pas le fonctionnement ?

Bah si ça a des chances d'être récolutionnaire, il va pas le donner

Probablement l'algorithme d'Euclide... Ce n'est pas impossible de le trouver au hasard, en s'amusant un peu.

Thibaut adore réinventer la roue

Mais c'est toi qui l'a trouvé et tu ne sais pas comment il marche ?

c'est vai que le meilleur et le plus rapide, sans doute, c'est une variante d'Euclide : au lieu de diviser, on prend la différence, c'est pas des divisions -> plus rapide et en itératif à la place de réucrsif, jusqu'à ce qu'un des termes soit nul et on prend l'autre.

C'est ce qu'il y a de plus simple, et j'ai pas encore trouvé mieux.

ça peut être long....
PGCD(1000000000,3)?

ah non! c'est vrai, il y en a un autre qui utilise l'écriture binaire d'un nombre!!

L'algorithme d'Euclide est très facile à coder en itératif!

unsigned long pgcd(unsigned long a,b) {
unsigned long c;
while(b) {
c=a%b;
a=b;
b=c;
}
return a;
}

(J'espère qu'il n'y a pas d'erreurs là-dedans.)

oui, mais tu as une division!! alors remplace la divison par une soustraction et ne fait l'échange que si il le faut, et c'est plus rapide!!

mais comme dit, le binaire est sans doute plus rapide là dedans.

oui, mais d'après mes souvenirs, tu auras un nombre de calculs bien plus importants avec la soustraction, donc p-e que c'est + rapide comme ça...

j'ai retrouvé!!

c'était :

PGCD(a,b)=
    2*PGCD(a/2,b/2) si a et b pairs
    PGCD(a/2,b) ou PGCD(a,b/2) si a ou b pair
    PGCD(a-b,b) ou PGCD(a,b-a) autrement selon le plus grand
    a si a=b

Mais j'ai retrouvé autre chose!!

tant que b>0
  r=min(a % b, b-a%b)
  a=b,b=r

a

C'est mieux, ça divise à peu près par deux, si mes souvenirs sont bons

[edit]Edité par Miles le 04-03-2002 à 20:43:12[/edit]

Kevin : Oui c'est exactement cet algo là que j'ai trouvé par hazard et par chance
Ca serait bien si je pouvais avoir autant de chance dans la vie de tous les jours

J'ai réinventé ce qu'a inventé Euclide, merde je ne peux pas déposer de brevet

Alors, quelqu'un a-t-il une demonstration expliquant (simplement, si possible) le fonctionnement cet algorithme ?
[edit]Edité par Thibaut le 04-03-2002 à 21:28:21[/edit]

facile!! - t'as vraiment jamais vu cet algo, même inconsciemment ? on le donne en général quand on parle de PGCD tout de suite au début -

soit d le résultat de l'algo. Je démontre que d|a et d|b ? je ne pense pas que ce soit utile.

donc d|PGCD(a,b)=c

a=k1*c, b=k2*c

PGCD(a,b)=k*d, donc on a a=k*k1*c et b=k*k2*c. Or on a d'après l'algo toujours une factorisation :
a=b*q+r, donc on peut factoriser par k*d, donc à la fin, on a k=1

Mal expliqué, mais c'est ça. faudrait faire ça correctement sous forme analyse synthèse en explicitant le truc que j'ai pas démontré.

>> t'as vraiment jamais vu cet algo, même inconsciemment ?
Je ne crois pas du tout. M'enfin peut-être inconsciemment, mais je te trouve assez tordu de me demander si même inconsciemment je ne l'aurais pas vu

Merci pour l'explication, je vais la potasser hors connexion

faut normalement commencer par démontrer ma première assertion - très simple - puis tu vérifies avec la synthèse. Très rapide, très simple - en interro cette année, j'ai dû le faire en moins de 5 min -

ah, oui, coût de mon deuxième algorithme : O(ln(a*b))

En effet, tous les deux appels, le produit a*b est au moins divisé par 2

Miles : "c'est vai que le meilleur et le plus rapide, sans doute, c'est une variante d'Euclide : au lieu de diviser, on prend la différence, c'est pas des divisions -> plus rapide et en itératif à la place de réucrsif "

C'est valable seulement sur des plateformes qui n'ont pas une instruction de division comme le cher Z80 (sur Gameboy par ex.). Sur un 68'000, je ne pense pas que ce soit plus rapide (à tester).

L'algo d'euclide peut etre generalisé .. au lieu d'etre dans le corp des reel pourquoi pas un corp vectoriel ou alors R[X]?

-- doublleu pauçte --
[edit]Edité par Thibaut le 06-03-2002 à 15:22:38[/edit]

Miles : bon j'ai rien compris à ton explication, trop dur pour mon niveau

je reprendrais l'explication bientôt...

Et pour les corps plus étendus, ça marche aussi, mais avec plutôt ma version que celle des autres...

pas des corps, mais des anneaux!! des anneaux euclidiens.

sans doute, mais un corps est un anneau, y'a juste euclidien que je ne sais plus...

Dans un corps, quelque soient a, b, c non nuls, c est un pgcd de a et b.
Donc la notion de pgcd n'a d'intérêt que dans un anneau qui n'est pas un corps.

Un anneau euclidien est un anneau A, avec une fonction phi : A\{0} -> N vérifiant :
pour tous x, y<>0, il existe q et r tels que x = q*y + r et ( r=0 ou phi(r)<phi(y) )
(égalité de division euclidienne)

Les anneaux euclidiens sont ceux dans lesquels on peut appliquer l'algorithme d'Euclide pour le pgcd.

Exemple :
Z, avec phi(x)=|x|
R[X], avec phi(p)=deg(p)

effectivement!! merci de ce rappel évident!!

A la limite, l'algo d'euclide peut etre interprétée dans un crop, puisque l'on a une lci ce qui suffit emplement... il faut alors etablir des relations d'ordres...