Discussion :

[progfou]

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 !

[pseudocode]

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é ?

??

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

[Zavonen]

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).

[progfou]

??

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.

[pseudocode]

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

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.