Euclide étendu

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

laurenth
Messages : 5
Inscription : lun. sept. 19, 2011 5:43 pm

Euclide étendu

Message par laurenth » mer. janv. 16, 2013 4:25 pm

Bonjour,

j'ai essayé d'implémenter l'algorithme d'Euclide étendu dans Z:

Code : Tout sélectionner

ixgcd(a,b):={ 
  local u0,u1,v0,v1,r0,r1,q;
    
  if (b=0) { return [sign(a),0,abs(a)]; };
  if (b<=0) {
    [u0,v0,r0] := ixgcd(a,-b);
    return [u0,-v0,r0]
  };
  
  u0, u1 := 1, 0; // on suppose que b>0
  v0, v1 := 0, 1;
  r0, r1 := a, b;

  while (r1!=0) {
    q := iquo(r0,r1);
    r0, r1 := r1, irem(r0,r1);
    u0, u1 := u1, u0-q*u1;
    v0, v1 := v1, v0-q*v1;
  };
  
  return [u0,v0,r0];
}:;
Ça marche, mais je me demande s'il n'y a pas plus élégant?

Le même algorithme donne des résultats faux pour les polynômes. Des suggestions?

Merci!

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

Re: Euclide étendu

Message par parisse » jeu. janv. 17, 2013 9:20 am

je pense qu'on peut enlever les tests au debut.
On peut utiliser des listes pour rendre le code plus compact

Code : Tout sélectionner

ixgcd(a,b):={ 
 local l1,l2; 
 l1:=[1,0,a];
 l2:=[0,1,b];
 tantque l2[2]!=0 faire
  l1,l2:=l2,l1-iquo(l1[2],l2[2])*l2;
 ftantque;
 return l1;
}:;
Pour les polynomes, il faut utiliser quo au lieu de iquo.

laurenth
Messages : 5
Inscription : lun. sept. 19, 2011 5:43 pm

Re: Euclide étendu

Message par laurenth » jeu. janv. 17, 2013 10:04 am

Merci! Très impressionnant...

Il faut maintenant que je comprenne ce qui cloche dans mon algorithme pour que les résultats soient faux.

Répondre