Re: foursquares.gp

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Nov 19, 2023 at 06:29:33PM +0100, hermann@stamm-wilbrandt.de wrote:
> Bill,
> 
> foursquares() does not only have a runtime problem for going direction of
> largest Mersenne prime.
> It did use 10.5GB RAM short before end of 12:11h run:
> 
> 
> Since when applying "foursquares()" to a Mersenne prime we know that the
> first "is_fact()" call is true ...
> 
> ? isfact(2^756839-1)
> 1
> ? ##
>   ***   last result computed in 1h, 12min, 11,683 ms.

This is the cost of checking that 2^756839-1 is prime...

> ? sq=foursquares_fact(2^756839-1);
>   ***   at top-level: sq=foursquares_fact(2^756839-1)
>   ***                    ^----------------------------
>   ***   in function foursquares_fact: abs(
>   ***   qfsolve(matdiagonal([1,1,1,1,-n]))[1..4])~
>   ***   ^------------------------------------------
>   *** qfsolve: the PARI stack overflows !
>   current stack size: 15000002560 (14305.117 Mbytes)
>   [hint] you can increase 'parisizemax' using default()
> 
>   ***   Break loop: type 'break' to go back to GP prompt
> break>
> 
> 
> How can it be that computing "sq=foursquares(2^756839-1);" worked (which
> calls foursquares_fact()), and calling
> it directly fails?

The algorithm is randomized. Also it is wasting a bit of memory.
If you find an example which is faster to reproduce, I can improve that.

Cheers,
Bill