Variantes de l'algorithme d'Euclide
Publié : lun. nov. 01, 2010 10:28 am
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:
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):
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
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.
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))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);