Finalement c'est dans les vieux pots qu'on fait les meilleures soupes! L'algorithme d'Euclide a des variantes (récursive ou itérative, à base de divisions euclidiennes ou de soustractions itérées) et il peut être intéressant (et tout-à-fait abordable en Seconde voire avant) de les comparer du point de vue du temps d'exécution (pour la mémoire, la version récursive est difficile à évaluer).
Alors voilà 4 versions:
Code : Tout sélectionner
pgcd_recur(a,b):={
local reste;
reste:=irem(a,b);
if (reste=0) then return b;
else return pgcd_recur(b,reste);
end_if;
};
pgcd_div(a,b):={
local x, y, t;
x:=a;
y:=b;
while (y>0){
t:=irem(x,y);
x:=y;
y:=t;
}
return x;
};
pgcd_sub(a,b):={
local x, y, t;
x:=a;
y:=b;
while (y>0){
t:=max(x,y)-min(x,y);
x:=min(x,y);
y:=t;
}
return x;
};
pgcd_2var(a,b):={
local x, y;
x:=a;
y:=b;
while(x!=y){
if(x>y) then x:=x-y;
else y:=y-x;
end_if;
}
};
Ensuite, on peut calculer les temps de calcul de tous les pgcd de n et 120, pour n allant jusqu'à 120 (qui dépendent grandement de n):
Code : Tout sélectionner
recur:=seq(time(pgcd_recur(n,120))[0],n=1..120))
divisio:=seq(time(pgcd_div(n,120))[0],n=1..120))
soustr:=seq(time(pgcd_sub(n,120))[0],n=1..120))
deuxvar:=seq(time(pgcd_2var(n,120))[0],n=1..120))
Afficher les "courbes" avec
plotlist, même en plusieurs couleurs, n'apporte pas grand-chose parce que les "courbes" sont trop chaotiques. Cependant, on voit que la méthode par soustractions avec troisième variable (les max-min) est toujours la plus lente de toutes, suivie par la méthode des soustractions avec seulement deux variables (source de cette méthode: [url=http://apmep_reunion.pagesperso-orange.fr/rallye/2010/R2010-Sujet_d%E9finitif.pdf]le Rallye mathématique 2010 de la Réunion[/url]), puis par la méthode récursive, et la méthode la plus rapide est toujours la méthode itérative basée sur les divisions euclidiennes.
Alors
Code : Tout sélectionner
color(plotlist(seq(soustr[k]/deuxvar[k],k=1..119)),2); color(plotlist(seq(recur[k]/divisio[k],k=1..119)),4);
permet de voir que la méthode des soustractions avec max-min prend environ 1,5 fois plus de temps que la méthode du Rallye 2010, et que la méthode récursive prend de 1 à 2 fois plus de temps que la méthode par divisions itérées.