Thank you very much for immediate answer and code fix. Seems your patch works
fine.
Best wishes,
Daniel Błażewicz
Od: "Alexander Hulpke" <hul...@math.colostate.edu>
Do: "Daniel Blazewicz" <kla...@interia.pl>;
Wysłane: 19:12 Poniedziałek 2014-12-29
Temat: Re: [GAP Forum] GaloisType is running very long
> Dear Forum, Dear Daniel Blazewicz,
>
> > I was executing GaloisType method for several irreducible polynomials of
> > the form x^12+ax+b to find solvable examples. And my loop "hung" at
> > x^12+63*x-450. After 2 days I decided to break the execution. FYI, I use 4
> > years old laptop with ~2GHz CPU. Do you know if it is expected that
> > GaloisType method can take days (weeks?) for polynomials of 12th degree?
>
> Yes and No.
>
> Why No:
> In your case there actually is a minor bug (a routine for approximating a
> root iterates between two approximations without stopping). This will be
> fixed in the next release. Thank you very much for reporting it. (I append
> the (pathetic -- it shows my lack of knowledge of numerical analysis) routine
> if you want an immediate patch.)
>
> What I would recommend for a search like yours is to call
> ProbabilityShapes
> on the polynomial first. If it returns S_n (or A_n) as only possibilities --
> and this will happen in most cases -- the result is correct and you
> presumably can eliminate the polynomial.
>
> Why Yes:
> If you happen upon a polynomial whose Galois group is M_{12} the certificate
> for distinguishing it from A_{12} is very expensive. Such a calculation will
> possibly take weeks. (ProbabilityShapes should be done always quickly, but
> does not guarantee that a Galois group cannot be larger.)
>
> Best wishes,
>
> Alexander Hulpke
>
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hul...@math.colostate.edu, Phone: ++1-970-4914288
> http://www.math.colostate.edu/~hulpke
>
>
> BindGlobal("ApproximateRoot",function(arg)
> local r,e,f,x,nf,lf,c,store,letzt;
> r:=arg[1];
> e:=arg[2];
>
> store:= e<=10 and IsInt(r) and 0<=r and r<=100;
> if store and IsBound(APPROXROOTS[e]) and IsBound(APPROXROOTS[e][r+1])
> then return APPROXROOTS[e][r+1];
> fi;
>
> if Length(arg)>2 then
> f:=arg[3];
> else
> f:=10;
> fi;
> x:=RootInt(NumeratorRat(r),e)/RootInt(DenominatorRat(r),e);
> nf:=r;
> c:=0;
> letzt:=[];
> repeat
> lf:=nf;
> Add(letzt,x);
> x:=ApproxRational(1/e*((e-1)*x+r/(x^(e-1))),f+6);
> nf:=AbsInt(x^e-r);
> if nf=0 then
> c:=6;
> else
> if nf>lf then
> lf:=nf/lf;
> else
> lf:=lf/nf;
> fi;
> if lf<2 then
> c:=c+1;
> else
> c:=0;
> fi;
> fi;
> # until 3 times no improvement
> until c>2 or x in letzt;
> if store then
> if not IsBound(APPROXROOTS[e]) then
> APPROXROOTS[e]:=[];
> fi;
> APPROXROOTS[e][r+1]:=x;
> fi;
> return x;
> end);
>
>
>
>
>
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
