factor

Bugs

Modérateur : xcasadmin

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

Re: factor

Message par frederic han » lun. oct. 21, 2013 9:28 am

avec le paquet amd64-19 ce factor tourne fou pour moi:

Code : Tout sélectionner

-135/14*a^2*b^2*c^2+270/7*a^2*b^2*c*d-9/4*a^2*b^2*c+9*a^2*b^2*d-135/7*a^2*b*c^2+540/7*a^2*b*c*d-9/2*a^2*b*c+18*a^2*b*d-135/14*a^2*c^3+270/7*a^2*c^2*d+477/28*a^2*c^2-477/7*a^2*c*d+9/2*a^2*c-18*a^2*d-9/4*a*b^4*c+9*a*b^4*d-99/7*a*b^2*c^3+18*a*b^2*c^2*d+207/14*a*b^2*c^2+9*a*b^2*c*d+18*a*b^2*c-54*a*b^2*d-198/7*a*b*c^3+36*a*b*c^2*d+270/7*a*b*c^2-18*a*b*c*d+36*a*b*d-99/7*a*c^4+18*a*c^3*d+1269/28*a*c^3-36*a*c^2*d-207/7*a*c^2-9*a*c-9/4*b^4*c^2+9/2*b^4*c-9/2*b^2*c^4+27/4*b^2*c^3+18*b^2*c^2-27*b^2*c-9*b*c^4+45/2*b*c^3-18*b*c^2+18*b*c-9/2*c^5+18*c^4-18*c^3
(cf le l[42] du test-factor3.cas)
J'ai mis d'autres test la:
http://www.math.jussieu.fr/~han/xcas/tests

Fred

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

Re: factor

Message par parisse » lun. oct. 21, 2013 11:04 am

en effet, bug d'algebre lineaire...

Code : Tout sélectionner

diff vecteur.cc vecteur.cc~
4178c4178
<       vector<int>::iterator it1=v1.begin()+cstart,it1end=v1.end(),it1_;
---
>       vector<int>::iterator it1=v1.begin()+cstart,it1end=v1.end(),it1_=it1end-4;
4181d4180
<       it1_=it1end-4;

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

Re: factor

Message par frederic han » mar. oct. 22, 2013 12:13 pm

Ca marche bien, cette fois je passe les 5000 tests sans problemes sous sage.

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

Re: factor

Message par parisse » mar. oct. 22, 2013 12:40 pm

5000! mazette, ca en fait!

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

Re: factor

Message par frederic han » jeu. nov. 14, 2013 5:38 pm

J'ai l'impression d'avoir un nouveau probleme, cette fois en faisant des essais avec des poly plus compliques:

Code : Tout sélectionner

p1,p2,p3:=(-4/5*a^2*b^3*c^5 + 3*a^6*b*c^2*d - 1/26*b^7*c^2*d + 2/3*a^4*b^2*c^3*d -13/4*a^2*b^3*c^3*d^2 - 1/5*a*b^4*c^4 + 1/2*b*c^8 - a^5*b*c*d^2 -a^3*b^3*d^3 - 2*b*c^5*d^3 + a^5*b^3 - a^3*c^3*d^2 - b*c^2*d^5 +1/8*a^4*b^3 - 1/20*a^5*c^2 - 4*a^4*b*d^2 - a*b*c^3*d^2 + 4/35*a^3*d^4 -6*b^2*d^5 + 2/7*b^2*c^4 + 1/75*b^2*d^4 + 1/4*a^3*b*c - b*c^2*d^2,-8*a^4*b^6 - 2*a^7*d^3 - 4*a^5*c^2*d^3 + 4*c^7*d^3 + 4*a^4*b*c^3*d +4*a*b*c^4*d^3 + 8*b*c^5*d^3 - 2*a^2*b^2*c*d^4 + 2*a^2*b^3*c^2*d +112*a^3*b*c^3*d + b^3*c^3 + 4*b^5*d + 4*a^3*b*d^2 - 12*a*b^3*d -16*a^2*c*d + 2*b^2*d, -1/7*a^2*b^2*c + 2/9*c^5 + a^3*c*d - 2*a^2*b*c -6*b*c^3 - 4*a*c*d - 2*a*d^2 - 76/3*b*d^2 + 22*a*b);
p:=normal(p1*p2*p3):;
np:=numer(p);
nops(factor(np % 101));
nops(factor(p));
alors le factor % 101 dit:
"Factorisation sur un corps fini à plusieurs variables nécessite un polynôme unitaire régulier en 0. Essayez de translater par rapport à une variable Erreur: Valeur Argument Incorrecte"

et le factor sur Q m'a donne des plantages
Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffff2682700 (LWP 30937)]
_int_malloc (av=0x7fffec000020, bytes=977) at malloc.c:3894
3894 malloc.c: Aucun fichier ou dossier de ce type.

ou parfois n'aboutit pas, alors qu'en xcas1.0.0 32bits j'ai les 3 facteurs en 2s

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

Re: factor

Message par parisse » jeu. nov. 14, 2013 6:35 pm

Je suppose que ce sont les garde-fous rajoutés récemment qui font échouer la factorisation par remontée de Hensel, du coup l'algorithme "heuristique" est lancé et il doit y avoir un overflow. Il faudra un jour reprendre ce code pour comprendre réellement quand ces gardes-fou sont nécessaires ...

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

Re: factor

Message par frederic han » ven. nov. 15, 2013 6:32 am

Mais si c'est cela, je ne vois pas le rapport avec l'erreur modulo 101 (ou un autre nombre premier) lorsque l'on demande la factorisation du numerateur. xcas100 y arrive aussi modulo 101 sans problemes.

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

Re: factor

Message par parisse » ven. nov. 15, 2013 7:13 am

Si, si, c'est le meme algorithme avec remontee de Hensel qui est utilise, mais en cas d'echec il n'y a pas de methode de rechange modulo p.

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

Re: factor

Message par parisse » sam. nov. 16, 2013 2:10 pm

Bon, je pense pouvoir enlever un des garde-fou en tenant compte de l'utilisation d'un des facteurs, par contre je laisse l'autre garde-fou sinon un de tes tests ne marche pas, ce qui impose d'augmenter une limite numerique (300->1000) pour pouvoir factoriser ton dernier polynome.

Code : Tout sélectionner

diff ezgcd.cc ezgcd.cc~
418,419c418
< 	// fx1x2 contains factorization of pcur(x1,x2,0,...0)
< 	// now find factorization of lcoeff(pcur)(x2,...,xn)
---
> 	// now find factorization of lcoeff(pcur)
423c422,423
< 	// if (gcd(pcur_lcoeff_sqfftest,pcur_lcoeff_sqfftest.derivative()).lexsorted_degree()) return false;
---
> 	if (gcd(pcur_lcoeff_sqfftest,pcur_lcoeff_sqfftest.derivative()).lexsorted_degree())
> 	  return false;
435c435
< 	} // flcoeff0 contains the list of factors of lcoeff(pcur) evaled at 0
---
> 	}
464c464
< 	      else {
---
> 	      else
466,468d465
< 		// mark jt->fact as used
< 		--jt->mult;
< 	      }
474c471
<       } // if is_one(pcurx1x2cont)
---
>       }
482,483c479,480
<     // (should also depends on the size of the coeffs and number of variables...)
<     if (!lcoeff_known && pow(lcp,s-1).coord.size()>1000)
---
>     // (depends on the size of the coeffs)
>     if (!lcoeff_known && pow(lcp,s-1).coord.size()>300)

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

Re: factor

Message par frederic han » lun. nov. 18, 2013 9:43 pm

Salut,
j'ai fait d'autres tests (avec le source du 18/11 en 64 bits)

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

celui pour j:=2 plante cette version de giac:
Program terminated with signal SIGKILL, Killed.

(et passe avec xcas10032bits)
il passe aussi modulo 101.

D'autre part, si je fais d'abord
factor(numer(p) % 101)

alors factor(p) passe ensuite en 150s.

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

Re: factor

Message par parisse » mar. nov. 19, 2013 1:25 pm

Etonnant, il passe en 32 bits!! Ca ne va pas me faciliter la tache de debug...

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

Re: factor

Message par parisse » mar. nov. 19, 2013 3:13 pm

J'ai rajoute 5 essais aleatoires de factorisation a la Hensel, celui-la passe, reste a voir pour les autres...

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

Re: factor

Message par frederic han » mar. nov. 19, 2013 10:12 pm

Oui c'est mieux, les 50 tests passent.

J'ai fait cette fois des essais de pgcd avec des polynomes du meme genre mais plus gros:
http://www.math.jussieu.fr/~han/xcas/tests/t5.cas

Cette fois je n'ai pas de plantage mais l'exemple 3 est anormalement long. modgcd le fait en 0.3s

a+

Fred

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

Re: factor

Message par parisse » mer. nov. 20, 2013 9:24 am

Oui, il y a une optimisation qui bugge, je la commente en attendant de voir pourquoi si j'ai le temps.

Code : Tout sélectionner

diff gausspol.cc gausspol.cc~
2056,2057c2056
<     // FIXME check degrees if comment false below, otherwise failure on biggcd
<     if (false && 
---
>     if (//false && 
Par contre, modgcd est plus rapide, parce que le choix de permutation de variable fait par gcd n'est pas optimal en vitesse dans ce cas. Il utilise le degree partiel minimum des 2 polynomes, ici c'est donc d qui est choisi comme variable principale et non a (degree min 25 contre 33). Mais le lcoeff de p1 et p2 n'a qu'un seul terme en a et 2 en d, il faudrait peut-etre que j'en tienne compte dans le choix fait par la fonction exchange_variables

Répondre