Variantes de l'algorithme d'Euclide

Discussion sur l'enseignement de l'algorithmique avec Xcas au lycee
alain974
Messages : 104
Inscription : lun. mai 24, 2010 11:15 am

Variantes de l'algorithme d'Euclide

Message par alain974 » 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:

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.
Pièces jointes
eucl1.png
image
eucl1.png (10.65 Kio) Consulté 5946 fois

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Variantes de l'algorithme d'Euclide

Message par parisse » mar. nov. 02, 2010 9:23 am

Il y a un petit probleme si on veut utiliser le temps de calcul avec Xcas sur ces exemples, c'est que le temps passe a faire des operations arithmetiques est masque par le temps necessaire pour effectuer les autres operations (gestion de la boucle, operations de copies de variables). Il faudrait pouvoir tester avec un langage compile pour mieux apprecier l'efficacite des differents algorithmes.

Répondre