foursquares.gp

[hermann@stamm-wilbrandt.de]

Bill did develop and tuned foursquares.gp based on this thread:
https://pari.math.u-bordeaux.fr/archives/pari-users-2310/msg00003.html

You can find foursquares.gp in contributed GP scripts section:
https://pari.math.u-bordeaux.fr/Scripts/
https://pari.math.u-bordeaux.fr/Scripts/foursquares.gp


It does outperform my approach based on ternary quadratic forms to 
determine sum of 3 suqares as of now by far:
https://pari.math.u-bordeaux.fr/archives/pari-users-2311/msg00018.html


Today I did determine AMD 7600CPU runtime of foursquares(M_p) for 
Mersenne primes with these p ("x"), and runtimes [s] ("y"):
https://github.com/Hermann-SW/QuadraticRegression/blob/master/foursquares.py#L9-L10

    "x": [110503, 132049, 216091, 756839, 859433, 1257787],
    "y": [   207,    319,    864,  13898,  18810,   43917],

I used this Python script to find quadratic regression, and runtime is 
nearly perfectly quadratic in log(M_p,2)=p:

https://github.com/Hermann-SW/QuadraticRegression/blob/master/foursquares.png

I did quadratic regression on first 5 values, and projected runtime for 
6th value was 11.99h, quite close:

$ gp -q foursquares.gp
? sq=foursquares(2^1257787-1);
? ##
  ***   last result computed in 12h, 11min, 57,261 ms.
? #sq
4
? norml2(sq)==2^1257787-1
1
?

So quadratic in p runtime of foursquares() is cool.


What I want is to determine sum of 4 squares for largest known 
(Mersenne) prime M_82589933 ;-)

Unfortunately foursquares() projected runtime is 7.25 CPU years ...

pi@raspberrypi400:~/QuadraticRegression $ python foursquares.py
y = 3.357227772845801e-08x² - 0.007965146591818498x + 809.5756276612528
pi@raspberrypi400:~/QuadraticRegression $ gp -q
? x=82589933
82589933
? (3.357227772845801e-08*x^2 - 0.007965146591818498*x + 
809.5756276612528)/3600/24/365
7.2407005534959244711415291542012303400
?


So I will try to tune ternary quadratic form method for hopefully 
reasonable runtime of few days.

And look whether Bill's foursquares() can be sped up as well.

Regards,

Hermann.