Richard Heylen on Thu, 07 Nov 2013 18:22:21 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: ellgroup hangs for certain input on Version 2.6.2 (development git-0f10e3b)


I know that testing for irreducibiltiy is slow so don't do it. Why
does ellgroup go into a busy loop? Can't this be detected cheaply and
the you could have it return some junk quickly?
ellgroup for the examples you quoted would be likely to be quite slow
(understatement!) too so there should be very little performance
decrease in catching this non-terminating behaviour.

Richard

On 7 November 2013 16:45, Karim Belabas
<Karim.Belabas@math.u-bordeaux1.fr> wrote:
> * Richard Heylen [2013-11-07 11:47]:
>> I believe it's policy that functions don't bother to check for bad
>> input values in order to keep things fast. However, when a function
>> hangs using 100% CPU on bad input then I think it needs to be fixed
>> because this would be bad as part of a long running cpu intensive pari
>> script.
>>
>> Cheers!
>>
>> Richard
>>
>> ? aa=ffgen(Mod(1,3)*x^2+Mod(2,3)*x+Mod(1,3),'a)
>> %1 = a
>> ? e=ellinit([aa^3,0],aa);
>> ? ellgroup(e)
>
> Just don't use reducible polynomials as input to ffgen :-)
>
> Prompted by your mail, I included a test for irreducibility in ffgen but it's
> far too expensive in general:
>
> ? P=ffinit(nextprime(2^500),1009);
> time = 120 ms.
>
>
> Before:
> ? ffgen(P);
> time = 0ms.
>
> After:
> ? ffgen(P);   \\ runs out of memory if parisize < 800MB
> time = 5min, 23,092 ms.
>
> So I removed that new check.
>
> I kept a check for squarefree-ness, which is still usually more
> expensive than producing P itsel, but not much more; and does not use too much
> memory. But I still feel it's a waste...
>
> Cheers,
>
>     K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
> `