PGCD: quelle est la méthode la plus rapide

Bonjour tout le monde !

Je me pose la question de savoir quelle méthode pour déterminer le PGCD est la plus rapide ?

L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?

Ma question est simple, mais impossible de trouver des preuves avec graphiques mesurant le temps consommé...

Merci de m'éclairer !

Citation:

---

Envoyé par progfou

L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?

---

8O ??

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Citation:

---

L'algorithme d'Euclide fait intervenir les modulos, ce qui est lent sur la plupart des processeurs ou la soustraction successive, qui impose la récursivité ?

---

Simple mise au point, aucune de ces méthodes n'IMPOSE la récursivité. Il s'agit de récursivité terminale, l'implémentation en itératif est donc immédiate.
Cela dit la référence de Pseudocode est définitive (rien à ajouter).

Citation:

---

Envoyé par pseudocode

8O ??

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

---

Si ce qui te choque c'est que je ne sois pas tombé sur ce lien, tu m'en vois désolé ;).

Je te remercie pour cet excellent lien.

Citation:

---

Envoyé par progfou

Si ce qui te choque c'est que je ne sois pas tombé sur ce lien, tu m'en vois désolé ;).

---

:mouarf2:

C'est surtout "la soustraction successive qui impose la récursivité" qui m'a semblé louche. Généralement des "trucs successifs" ca impose plutot des itérations. :P