hermann on Fri, 06 Oct 2023 18:42:00 +0200


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

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

On 2023-10-06 16:04, Bill Allombert wrote:


This one is OK.

... but suboptimal, we should start by the largest i, so that P is as
small as possible!

foursquaref(n)=
{
  forstep(i=sqrtint(n),1,-1,
    my(P=n-i^2, v = valuation(P,2)\2);
    if (P/4^v%8!=7,
      my(F=factor(P,2^20)[,1]);
      if(ispseudoprime(F[#F]),
        return(concat(i,threesquare(P))))));
}


I tried that, for some values >100x faster than the other.
But still not good for really large numbers.

All but first Mersenne prime are =7 (mod 8), so needing 4 squares.
I tried some Mersenne primes 2^p-1 on fast AMD 7600X CPU:

p       time [min]
11213	0:02
21701	1:12
44497	2:08
86243   stooped after 46:00


I will look whether the presentation from this posting
https://pari.math.u-bordeaux.fr/archives/pari-users-2310/msg00011.html

and ternary and binary quadratic forms will allow to create sum
of three squares for odd n !=7 (mod 8) efficiently.


Stretch target: compute sum of 4 squares for Mersenne prime M51.


Regards,

Hermann.