Re: efficient foursquare() and/or threesquare1m4() functions

[hermann@stamm-wilbrandt.de]

On 2023-10-08 18:38, Bill Allombert wrote:
> I join a script that should handle all cases.
> (two/three/four squares with or without factorization, except
> for two squares without factoring, which I do not know how to do.)
Thanks, small typo:
...
fouresquares_fact(n)=abs(qfsolve(matdiagonal([1,1,1,1,-n]))[1..4])~
...

needs to be "...foursquares_fact...".

Works fine for reasonable sized numbers.
I did run it over night on fast AMD76000X CPU.
Takes 12h for 1.2million bit Mersenne prime (biggest has 57.8million 
bits).
Only application to those very big numbers makes me look to
implement threesquares() based on ternary quadratic form.

hermann@7600x:~$ gp -q 4sq.gp
? foursquares(2^4423-1);
? ##
  ***   last result computed in 113 ms.
? foursquares(2^21701-1);
? ##
  ***   last result computed in 3,925 ms.
? foursquares(2^44497-1);
? ##
  ***   last result computed in 22,550 ms.
? n=2^1257787-1;
? F=foursquares(n);
? ##
  ***   last result computed in 12h, 2min, 37,878 ms.
? vecsum([x^2|x<-F])==n
1
?

Regards,

Hermann.