Page 1 sur 1

division euclidienne de polynômes

Posté : sam. 20 mars 2010, 17:19
par ouagatex
Bonjour à tous,

Je produis tous mes dessins (cours, DS...) avec latex+Asymptote depuis quelque temps. J'ai beaucoup profité des contributions de Philippe Ivaldi et de Gaétan.
Je les en remercie chaleureusement.
Voici une modeste contribution. C'est une extension qui permet d'effectuer et de dessiner une division euclidienne de polynômes.
Ca traine depuis deux ans sur mon disque dur, si ça peut être utile à quelqu'un j'en serais content.
Je ne l'ai moi même qu'assez peu utilisée, elle est peut-être buggée: vérifier avec xcas ne coûte pas cher.

Edition par GM le 22/03 : une version modifiée du code suivant est proposée dans une réponse qui suit.

voici le fichier diveucl_dev.asy à mettre au bon endroit (sous linux dans ~/.asy/)

Code : Tout sélectionner

void diveucli(picture pic=currentpicture,
                real[] dividende,
                real[] diviseur,
                real xunite=12mm,
                real yunite=8mm)
{

unitsize(pic,xunite,yunite);

real[] divid,divis,sous;
divid=dividende;
divis=diviseur;
int l1=divid.length, l2=divis.length;
real a,b,p,q,s;
pair Q,S,D;
string ch;

for(int i=0; i < l1; ++i){
a=l1-i-1;
b=dividende[i];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             } 
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
draw(pic,ch,(i,0));
}
draw(pic,(l1,.5)--(l1,-3));
draw(pic,(l1,-.5)--(l1+l2+1,-.5));
for(int i=0; i < l2; ++i){
a=l2-i-1;
b=diviseur[i];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             } 
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
draw(pic, ch,(i+l1+1,0));
}

// on initialise les positions des polynomes
Q=(l1+1,-1);
S=(0,-1);
D=(0,-2);

while(divis.length<=divid.length){
//for(int i=0; i < 1; ++i){

p=divid.length-divis.length;
q=divid[0]/divis[0];

// on ecrit un bout de quotient
a=p;
b=q;
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             } 
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
draw(pic, ch,Q);

sous=q*divis;
s=sous.length;

// on ecrit ce qu'on soustrait au dividende
for(int j=0; j < s; ++j){
a=s-j-1+p;
b=sous[j];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             } 
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
draw(pic, ch,S+(j,0));
}

// on cree le nouveau dividende
l1=divid.length;
for(int j=0; j < l1-s; ++j){ sous.push(0);}
draw(pic,S+(-0.5,-0.5)--S+(s-0.5,-0.5));
divid=divid-sous;
l1=divid.length;

// on ecrit le nouveau dividende
for(int j=0; j < l1; ++j){
a=l1-j-1;
b=divid[j];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             } 
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
draw(pic, ch,D+(j,0));
}
// on vire les zeros du debut du dividende
a=0;
while(divid[0]==0){
divid.delete(0);
a=a+1;
}
Q=Q+(1,0);
S=S+(a,-2);
D=D+(a,-2);
}
}
et voici le code dessinant une petite division:

Code : Tout sélectionner

import diveucl_dev;
picture dessin;
real[] dividende={1,3,3,7,-34,16},diviseur={1,3,-2};
diveucli(dessin,dividende,diviseur,12mm,8mm);
shipout(dessin);

Re: division euclidienne de polynômes

Posté : sam. 20 mars 2010, 21:19
par GM
Je n'ai pas encore testé, je le ferai... mais déjà un grand merci pour l'intention. :)

Re: division euclidienne de polynômes

Posté : sam. 20 mars 2010, 23:41
par GM
ouagatex a écrit :Je ne l'ai moi même qu'assez peu utilisée, elle est peut-être buggée: vérifier avec xcas ne coûte pas cher.

Il y a une erreur avec l'exemple suggéré car x^2+3x-2 divise x^5+3x^4+3x^3+7x^2-34x+16 mais cela fonctionne en remplaçant par x^5+3x^4+3x^3+7x^2-34x+17.
Donc il y a apparemment une amélioration à apporter ... (pour le cas où le reste est nul ??).

Re: division euclidienne de polynômes

Posté : dim. 21 mars 2010, 14:40
par ouagatex
Ok, merci, je me penche sur la question!

Re: division euclidienne de polynômes

Posté : dim. 21 mars 2010, 23:14
par ouagatex
Mille excuses, je ne voyais pas le bug chez moi tout simplement parce que j'avais posté une vieille version de l'extension! Je me suis emmêlé les pinceaux :oops: .
J'ai en fait l'impression que le copier-coller que j'ai fait d'emacs n'a pas bien fonctionné. C'était une version qui trainait dans mon presse papier.

Voici donc diveucl_dev.asy qui annule et remplace mon code précédent:

Code : Tout sélectionner

void diveucli(picture pic=currentpicture,
                real[] dividende,
                real[] diviseur,
                real xunite=12mm,
                real yunite=8mm)
{

unitsize(pic,xunite,yunite);

real[] divid,divis,sous;
divid=dividende;
divis=diviseur;
int l1=divid.length, l2=divis.length;
real a,b,p,q,s;
pair Q,S,D;
string ch;

for(int i=0; i < l1; ++i){
a=l1-i-1;
b=dividende[i];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             }
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
label(pic,ch,(i,0));
}
draw(pic,(l1,.5)--(l1,-3));
draw(pic,(l1,-.5)--(l1+l2+1,-.5));
for(int i=0; i < l2; ++i){
a=l2-i-1;
b=diviseur[i];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             }
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
label(pic, ch,(i+l1+1,0));
}

// on initialise les positions des polynomes
Q=(l1+1,-1);
S=(0,-1);
D=(0,-2);

while(divis.length<=divid.length){
//for(int i=0; i < 1; ++i){

p=divid.length-divis.length;
q=divid[0]/divis[0];

// on ecrit un bout de quotient
a=p;
b=q;
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             }
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
label(pic, ch,Q);

sous=q*divis;
s=sous.length;

// on ecrit ce qu'on soustrait au dividende
for(int j=0; j < s; ++j){
a=s-j-1+p;
b=sous[j];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             }
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
label(pic, ch,S+(j,0));
}

// on cree le nouveau dividende
l1=divid.length;
for(int j=0; j < l1-s; ++j){ sous.push(0);}
draw(pic,S+(-0.5,-0.5)--S+(s-0.5,-0.5));
divid=divid-sous;
l1=divid.length;

// test pour savoir si le dividende est vide
bool bo=false;
for(int j=0; j< divid.length; ++j){bo= (bo | divid[j]!=0);}

// on ecrit le nouveau dividende
if(bo){
for(int j=0; j < l1; ++j){
a=l1-j-1;
b=divid[j];
if(b==0){ch="";} else{
if(a==0){
         if(0<b){ch="$+" + (string) b + "$";}
          else {ch="$" + (string) b + "$";}
        }
else{
     if(a==1){
              if(0<b){ch="$+" + (string) b+"x$";}
              else {ch="$" + (string) b+"x$";}
             }
     else{
          if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
          else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
         }
    }
}
label(pic, ch,D+(j,0));
}}
else{label(pic,"$0$",D+(divid.length-1,0));}

// on vire les zeros du debut du dividende
a=0;
while(divid[0]==0 & 1<divid.length){
divid.delete(0);
a=a+1;
}
Q=Q+(1,0);
S=S+(a,-2);
D=D+(a,-2);
}
}


Figure asymptote 16ebed4e00ade08afcddbdda38c91266
*** Pour masquer/découvrir le code Asymptote qui a permis de créer la figure, il faut cliquer dessus. ;-) ***

CODE ASYMPTOTE de la figure ci-dessus : Tout sélectionner
  1. void diveucli(picture pic=currentpicture,
  2. real[] dividende,
  3. real[] diviseur,
  4. real xunite=12mm,
  5. real yunite=8mm)
  6. {
  7. unitsize(pic,xunite,yunite);
  8. real[] divid=dividende,
  9. divis=diviseur,
  10. sous;
  11. int l1=divid.length,
  12. l2=divis.length;
  13. real a,b,p,q,s;
  14. pair Q,S,D;
  15. string ch;
  16.  
  17. for(int i=0; i < l1; ++i){
  18. a=l1-i-1;
  19. b=dividende[i];
  20. if(b==0){ch="";} else{
  21. if(a==0){
  22. if(0<b){ch="$+" + (string) b + "$";}
  23. else {ch="$" + (string) b + "$";}
  24. }
  25. else{
  26. if(a==1){
  27. if(0<b){ch="$+" + (string) b+"x$";}
  28. else {ch="$" + (string) b+"x$";}
  29. }
  30. else{
  31. if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
  32. else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
  33. }
  34. }
  35. }
  36. label(pic,ch,(i,0));
  37. }
  38. draw(pic,(l1,.5)--(l1,-3));
  39. draw(pic,(l1,-.5)--(l1+l2+1,-.5));
  40. for(int i=0; i < l2; ++i){
  41. a=l2-i-1;
  42. b=diviseur[i];
  43. if(b==0){ch="";} else{
  44. if(a==0){
  45. if(0<b){ch="$+" + (string) b + "$";}
  46. else {ch="$" + (string) b + "$";}
  47. }
  48. else{
  49. if(a==1){
  50. if(0<b){ch="$+" + (string) b+"x$";}
  51. else {ch="$" + (string) b+"x$";}
  52. }
  53. else{
  54. if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
  55. else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
  56. }
  57. }
  58. }
  59. label(pic, ch,(i+l1+1,0));
  60. }
  61.  
  62. // on initialise les positions des polynomes
  63. Q=(l1+1,-1);
  64. S=(0,-1);
  65. D=(0,-2);
  66.  
  67. while(divis.length<=divid.length){
  68. //for(int i=0; i < 1; ++i){
  69.  
  70. p=divid.length-divis.length;
  71. q=divid[0]/divis[0];
  72.  
  73. // on ecrit un bout de quotient
  74. a=p;
  75. b=q;
  76. if(b==0){ch="";} else{
  77. if(a==0){
  78. if(0<b){ch="$+" + (string) b + "$";}
  79. else {ch="$" + (string) b + "$";}
  80. }
  81. else{
  82. if(a==1){
  83. if(0<b){ch="$+" + (string) b+"x$";}
  84. else {ch="$" + (string) b+"x$";}
  85. }
  86. else{
  87. if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
  88. else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
  89. }
  90. }
  91. }
  92. label(pic, ch,Q);
  93.  
  94. sous=q*divis;
  95. s=sous.length;
  96.  
  97. // on ecrit ce qu'on soustrait au dividende
  98. for(int j=0; j < s; ++j){
  99. a=s-j-1+p;
  100. b=sous[j];
  101. if(b==0){ch="";} else{
  102. if(a==0){
  103. if(0<b){ch="$+" + (string) b + "$";}
  104. else {ch="$" + (string) b + "$";}
  105. }
  106. else{
  107. if(a==1){
  108. if(0<b){ch="$+" + (string) b+"x$";}
  109. else {ch="$" + (string) b+"x$";}
  110. }
  111. else{
  112. if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
  113. else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
  114. }
  115. }
  116. }
  117. label(pic, ch,S+(j,0));
  118. }
  119.  
  120. // on cree le nouveau dividende
  121. l1=divid.length;
  122. for(int j=0; j < l1-s; ++j){ sous.push(0);}
  123. draw(pic,S+(-0.5,-0.5)--S+(s-0.5,-0.5));
  124. divid=divid-sous;
  125. l1=divid.length;
  126.  
  127. // test pour savoir si le dividende est vide
  128. bool bo=false;
  129. for(int j=0; j< divid.length; ++j){bo= (bo | divid[j]!=0);}
  130.  
  131. // on ecrit le nouveau dividende
  132. if(bo){
  133. for(int j=0; j < l1; ++j){
  134. a=l1-j-1;
  135. b=divid[j];
  136. if(b==0){ch="";} else{
  137. if(a==0){
  138. if(0<b){ch="$+" + (string) b + "$";}
  139. else {ch="$" + (string) b + "$";}
  140. }
  141. else{
  142. if(a==1){
  143. if(0<b){ch="$+" + (string) b+"x$";}
  144. else {ch="$" + (string) b+"x$";}
  145. }
  146. else{
  147. if(0<b){ch="$+" + (string) b+"x^{" + (string) a + "}$";}
  148. else {ch="$" + (string) b+"x^{" + (string) a + "}$";}
  149. }
  150. }
  151. }
  152. label(pic, ch,D+(j,0));
  153. }}
  154. else{label(pic,"$0$",D+(divid.length-1,0));}
  155.  
  156. // on vire les zeros du debut du dividende
  157. a=0;
  158. while(divid[0]==0 & 1<divid.length){
  159. divid.delete(0);
  160. a=a+1;
  161. }
  162. Q=Q+(1,0);
  163. S=S+(a,-2);
  164. D=D+(a,-2);
  165. }
  166. }
  167.  
  168. picture dessin;
  169. real[] dividende={1,3,3,7,-34,16},diviseur={1,3,-2};
  170. diveucli(dessin,dividende,diviseur,12mm,8mm);
  171. shipout(dessin);


J'attends les prochains bugs :mrgreen:

Re: division euclidienne de polynômes

Posté : lun. 22 mars 2010, 13:54
par GM
ouagatex a écrit :Mille excuses, je ne voyais pas le bug chez moi tout simplement parce que j'avais posté une vieille version de l'extension !

Je me suis permis d'éditer ton premier message pour indiquer le message comportant la bonne version.

ouagatex a écrit :J'attends les prochains bugs :mrgreen:

Mais non, mais non... ;-)
Je testerai un peu plus tard. Merci.

Re: division euclidienne de polynômes

Posté : lun. 22 mars 2010, 17:16
par ouagatex
Je me suis permis d'éditer ton premier message pour indiquer le message comportant la bonne version.


pas de souci, merci

Je pense qu'il doit être assez simple "d'étendre" cette extension afin qu'elle effectue également les divisions euclidiennes d'entiers (à ce sujet je crois que Jean-Côme Charpentier a produit une extension latex qui pose les quatre opérations) . Si j'ai le temps un de ces jours, j'essaierai de voir ça.

Re: division euclidienne de polynômes

Posté : mer. 31 mars 2010, 11:02
par mumblee
ouagatex a écrit :Je pense qu'il doit être assez simple "d'étendre" cette extension afin qu'elle effectue également les divisions euclidiennes d'entiers (à ce sujet je crois que Jean-Côme Charpentier a produit une extension latex qui pose les quatre opérations) . Si j'ai le temps un de ces jours, j'essaierai de voir ça.

C'est xlop