factor

Bugs

Modérateur : xcasadmin

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

factor

Message par frederic han » mar. oct. 08, 2013 8:03 pm

Salut,

Je n'ai pas ce probleme avec le paquet debian 1.1.0-17 amd 64, en revanche, si je compile par exemple le source du 8/10 j'ai ce probleme:

Code : Tout sélectionner

f:=72/5*a^2*b^2*c*d+72/115*a^2*b*c^2*d+2016/5*a^2*b*c*d^2-12/5*a^2*b*c*d+432/5*a^2*b*c+432/23*a^2*c^2*d^2-864*a^2*c*d^3-72*a^2*c*d^2+2592*a^2*c*d-24/5*a*b^4*d-24/115*a*b^3*c*d-672/5*a*b^3*d^2+4/5*a*b^3*d-144/5*a*b^3+384/115*a*b^2*c*d^2+288*a*b^2*d^3+24*a*b^2*d^2-133872/155*a*b^2*d-16512/115*a*b*c^2*d^2+1584/5*a*b*c*d^3-8/5*a*b*c*d^2+205392/3565*a*b*c*d+1344/155*a*b*d^2-8/155*a*b*d+288/155*a*b-144/23*a*c^3*d^2+6960/23*a*c^2*d^3+24*a*c^2*d^2-864*a*c^2*d-672*a*c*d^4-56*a*c*d^3+1437696/713*a*c*d^2-576/31*a*d^3-48/31*a*d^2+1728/31*a*d+48*b^3*c*d^2-16*b^3*d^3+48/23*b^2*c^2*d^2-2224/23*b^2*c*d^3-8*b^2*c*d^2+288*b^2*c*d+32*b^2*d^4+8/3*b^2*d^3-96*b^2*d^2-96*b*c^2*d^3+32*b*c*d^4-96/31*b*c*d^2+32/31*b*d^3-96/23*c^3*d^3+4448/23*c^2*d^4+16*c^2*d^3-410784/713*c^2*d^2-64*c*d^5-16/3*c*d^4+141344/713*c*d^3+16/31*c*d^2-576/31*c*d-64/31*d^4-16/93*d^3+192/31*d^2;
factor(f)
donne:

Unable to divide, perhaps due to rounding error%%%{700569,[0,2,2,0]%%%}+%%%{1401138,[0,2,1,0]%%%}+%%%{700569,[0,2,0,0]%%%}+%%%{127503558,[0,1,2,0]%%%}+%%%{255007116,[0,1,1,0]%%%}+%%%{127503558,[0,1,0,0]%%%}+%%%{5801411889,[0,0,2,0]%%%}+%%%{11602823778,[0,0,1,0]%%%}+%%%{5801411889,[0,0,0,0]%%%} / %%%{279,[0,1,1,0]%%%}+%%%{279,[0,1,0,0]%%%}+%%%{8370,[0,0,1,1]%%%}+%%%{25389,[0,0,1,0]%%%}+%%%{8370,[0,0,0,1]%%%}+%%%{25389,[0,0,0,0]%%%} Error: Bad Argument Value"
// Time 0.01

plus precisement, si apres cette erreur je fais un second factor(f) alors ca marche!

si je fais un restart ca recommence.

Quelqu'un arrive t'il a le reproduire ou bien est ce un probleme de ma compilation?

Frederic

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

Re: factor

Message par parisse » mer. oct. 09, 2013 6:34 am

Je n'arrive pas a reproduire. J'ai essaye 8 factor de suite (vu que ton probleme semble relie a l'utilisation du generateur aleatoire dans l'algo de factorisation), les 8 fonctionnent.

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » mer. oct. 09, 2013 7:23 am

Effectivement, j'ai pas mal de polynomes similaires qui passent, mais par exemple si je fais cela sous sage avec le spkg:

Code : Tout sélectionner

P.<a,b,c,d>=QQ[]
for i in range(1,100):
     p1=ZZ.random_element(1,5)*P.random_element()
     p2=ZZ.random_element(1,5)*P.random_element()
     p3=ZZ.random_element(1,5)*P.random_element()
     p=(libgiac(p1)*libgiac(p2)*libgiac(p3)).normal()
     print
     print p
     f=p.factors()
les 29 premiers passent sans problème mais pas le 30.
Est ce que c'est mon spkg (qui a pari desactivé) qui pose problème?

Fred

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

Re: factor

Message par parisse » mer. oct. 09, 2013 8:42 am

Il me faudrait un input giac qui buggue reproductible, debugguer dans sage ca serait trop galere, vu qu'il faut s'attacher a un process avec gdb...

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » mer. oct. 09, 2013 11:48 am

ca me le fait aussi avec la version de giac du spkg:

on peut se mettre en shell via sage:

sage -sh

puis:

giac ou gdb giac

Alors le poly donne plante pour moi et toi?

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » mer. oct. 09, 2013 12:22 pm

Bon j'y arrive aussi avec le deb mais plus loin:

http://www.math.jussieu.fr/~han/xcas/full_output.cas

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

Re: factor

Message par parisse » mer. oct. 09, 2013 1:38 pm

Voila ce qui plante

Code : Tout sélectionner

f:=3/5*a^2*b^2*c^2+129/20*a^2*b*c^3+18/5*a^2*b*c^2*d-1443/40*a^2*b*c^2+387/10*a^2*c^3*d-387*a^2*c^3-9/20*a^2*c^2*d+9/2*a^2*c^2-273/5*a*b^2*c^2*d+3/5*a*b^2*c^2-11739/20*a*b*c^3*d+129/20*a*b*c^3-18/5*a*b*c^2*d^2+1857/40*a*b*c^2*d-1443/40*a*b*c^2-387/10*a*c^3*d^2+4257/10*a*c^3*d-387*a*c^3+9/20*a*c^2*d^2-99/20*a*c^2*d+9/2*a*c^2+54*b^2*c^2*d^2-54*b^2*c^2*d+1161/2*b*c^3*d^2-1161/2*b*c^3*d-27/4*b*c^2*d^2+27/4*b*c^2*d;
factor(f);
C'est dans le code de factorisation multi-variables avec remontee de Hensel, ca va pas etre simple...

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

Re: factor

Message par parisse » mer. oct. 09, 2013 5:22 pm

Bon, j'ai un fix simple, sans doute pas optimal, mais bon...

Code : Tout sélectionner

diff ezgcd.cc ezgcd.cc~
412c412
<       if (is_one(pcurx1x2cont)){
---
>       if (1 || is_one(pcurx1x2cont)){

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » jeu. oct. 10, 2013 4:16 am

Donc j'ai enleve le
1||

ca a l'air de mieux marcher mais j'ai aussi cette erreur sur les 2 versions:

Code : Tout sélectionner

0>> f:=-16/3*a^3*b*c^2-64*a^3*b*c*d+256/3*a^3*b*c+1408*a^3*b*d+704*a^3*b+16*a^3*c^2*d-16/9*a^3*c^2+192*a^3*c*d^2-832/3*a^3*c*d+256/9*a^3*c-4224*a^3*d^2-4928/3*a^3*d+704/3*a^3+4/3*a^2*b*c^3+16*a^2*b*c^2*d-1328/15*a^2*b*c^2-16/3*a^2*b*c*d^2-3792/5*a^2*b*c*d+6064/5*a^2*b*c-64*a^2*b*d^3-32*a^2*b*d^2+8096*a^2*b*d+1008/5*a^2*c^2*d-112/5*a^2*c^2+16*a^2*c*d^3+54784/45*a^2*c*d^2-64528/15*a^2*c*d+6944/15*a^2*c+192*a^2*d^4+224/3*a^2*d^3-72896/3*a^2*d^2+8096/3*a^2*d+84/5*a*b*c^3+4/3*a*b*c^2*d^2+508/5*a*b*c^2*d-1928/5*a*b*c^2+16*a*b*c*d^3-56*a*b*c*d^2-11224/5*a*b*c*d-368*a*b*d^3+576/5*a*c^2*d-64/5*a*c^2+192*a*c*d^3+9616/15*a*c*d^2-368/5*a*c*d+1104*a*d^4-368/3*a*d^3+48/5*b*c^3+16*b*c^2*d^2+276/5*b*c^2*d+92*b*c*d^3:;
"Done"
// Time 0
1>> factor(f)
"Puissance négative de polynôme Erreur: Valeur Argument Incorrecte"
// Time 0

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

Re: factor

Message par parisse » jeu. oct. 10, 2013 7:40 am

petit bug, petit fix, ouf:-)

Code : Tout sélectionner

diff gausspol.cc gausspol.cc~
5121c5121
<     Tnextcoeff<gen>(it,itend); // ++it;
---
>     ++it;

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » jeu. oct. 10, 2013 8:21 pm

Salut, j'ai l'impression qu'il m'en reste encore un peu, ca m'arrive moins souvent, mais par exemple avec ce polynome:

Code : Tout sélectionner

f:=16*a^3*b^2-24*a^3*b*d+16*a^2*b^3*c-48*a^2*b^3-40*a^2*b^2*c*d-1232*a^2*b^2*c+72*a^2*b^2*d+24*a^2*b*c*d^2+1848*a^2*b*c*d+16*a^2*b*d^2+12*a^2*b*d-24*a^2*d^3-1248*a*b^3*c^2+3744*a*b^3*c+3120*a*b^2*c^2*d-1248*a*b^2*c^2+16*a*b^2*c*d^2-5604*a*b^2*c*d-48*a*b^2*d^2-36*a*b^2*d-1872*a*b*c^2*d^2+1872*a*b*c^2*d-40*a*b*c*d^3+4*a*b*c*d^2-924*a*b*c*d+72*a*b*d^3+24*a*c*d^4-24*a*c*d^3+12*a*d^3-936*b^2*c^2*d+2808*b^2*c*d+936*b*c^2*d^2-936*b*c^2*d+12*b*c*d^3-36*b*d^3-12*c*d^4+12*c*d^3
j'arrive a le factoriser une ou 2 fois mais si je redemande pas mal sa factorisation alors je finis par avoir le:
"Division euclidienne non exacte, peut-être des erreurs d'arrondis%%%{6084,[0,2,0,0]%%%}+%%%{36504,[0,1,0,0]%%%}+%%%{54756,[0,0,0,0]%%%} / %%%{78,[0,2,0,0]%%%}+%%%{-78,[0,1,1,0]%%%}+%%%{468,[0,1,0,0]%%%}+%%%{-234,[0,0,1,0]%%%}+%%%{702,[0,0,0,0]%%%} Erreur: Valeur Argument Incorrecte"


avec:

le paquet debian -18 ou le source du 10/10

toi aussi?

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

Re: factor

Message par parisse » ven. oct. 11, 2013 6:56 am

je n'ai pas le courage de m'en assurer, mas je pense que c'est parce qu'un des polynomes generes aleatoirement n'est pas square-free. Voila le diff qui regle le cas de ton polynome:

Code : Tout sélectionner

diff ezgcd.cc ezgcd.cc~
419,423c419
< 	polynome pcur_lcoeff(Tfirstcoeff(pcur)),pcur_lcoeffcont,pcur_lcoeff_sqfftest;
< 	peval_xk_xn_zero(pcur_lcoeff,2,pcur_lcoeff_sqfftest);
< 	pcur_lcoeff_sqfftest=pcur_lcoeff_sqfftest.trunc1();
< 	if (gcd(pcur_lcoeff_sqfftest,pcur_lcoeff_sqfftest.derivative()).lexsorted_degree())
< 	  return false;
---
> 	polynome pcur_lcoeff(Tfirstcoeff(pcur)),pcur_lcoeffcont;

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » ven. oct. 11, 2013 8:32 am

Super,

cette fois ci je passe 2000 tests sans problemes depuis sage.
Fred

frederic han
Messages : 1113
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: factor

Message par frederic han » ven. oct. 11, 2013 10:08 am

Salut,
en amd64 avec le deb -18 j'arrive ce poly sans problemes (3 a 4 secondes).

http://www.math.jussieu.fr/~han/xcas/poly2.cas
en 32 bits, avec les modifiactions precedentes j'ai:

Code : Tout sélectionner

giac poly2.cas
// Maximum number of parallel threads 16
// Giac share root-directory:/scratch/han/sage-5.12/local/share/giac/
// Giac share root-directory:/scratch/han/sage-5.12/local/share/giac/
// Using keyword file /scratch/han/sage-5.12/local/share/giac/doc/fr/keywords
// Giac share root-directory:/scratch/han/sage-5.12/local/share/giac/
Help file /scratch/han/sage-5.12/local/share/giac/doc/fr/aide_cas not found
Added 172 synonyms
4,
// Time 1.99
"Done",
// Time 0.11
8314,
// Time 0.1
GNU MP: Cannot reallocate memory (old_size=4 new_size=283492)
Abandon

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

Re: factor

Message par parisse » ven. oct. 11, 2013 10:27 am

Les modifs font que l'algorithme de Hensel pour factoriser echoue un peu plus souvent, et dans ce cas, c'est un algo du meme type que le PGCD heuristique, on evalue les variables sur des entiers, qui sont de plus en plus grands s'il y a plus de 2 variables, donc ca peut engendrer des problemes de memoire.
Il faudrait prendre le temps de voir precisement pourquoi le code de Hensel ne marche pas dans les cas que tu m'as soumis, je me suis contente d'extraire une cause previsible d'erreur (evaluation non square-free), et je l'ai corrige au plus vite en renvoyant vers l'algorithme heuristique...
Bon pour l'instant je suis dans les bases de Groebner, sans doute pour un bon moment encore. Je retravaillerai la factorisation multi-variables plus tard...

Répondre