Re: Question on ternary quadratic form

[hermann@stamm-wilbrandt.de]

On 2023-11-17 11:39, Bill Allombert wrote:
> > Your "foursquares()" takes 21ms for M_1279.
> > But I had to stop it after more than an hour for M_2203 on i7-11850H 
> > CPU.
>
> This is strange, do you have the latest version ?
>
> ? foursquares(2^1279-1)
> time = 12 ms.
> ? foursquares(2^2203-1)
> time = 31 ms.
> ? foursquares(2^9689-1)
> time = 684 ms.
>
> Cheers,
> Bill.
I did download again and verified that I had last version.
I did run "foursquares(M_p)" again, 8ms for 1279, did stop after more 
than 40min for 2203:

gp version is 2.15.3 on RHEL 8.8 and i7-11850H CPU, that was bad.
With gp 2.16.1 on Ubuntu 22.04 on AMD 7600X "foursquares()" is much 
better.
And outperforms tqf.gp "squares34()" for Mersenne primes.
See the runtime table in updated comment:

https://gist.github.com/Hermann-SW/f13b8adf7d7e3094f0b6db0bce29a7b8?permalink_comment_id=4763152#gistcomment-4763152


For tqf.gp nearly all runtime is spent in this loop:

        for(vv=0,oo,
            if(ispseudoprime((4*vv+1)*n-1),
                v=vv; break()));

There is a randomization in this paper ...
https://pollack.uga.edu/finding3squares-6.pdf

... which computes the needed prime much faster.
I will try to speed up tqf.gp based on that paper.


For the higher values in table for foursquares(M_p) a simple
analysis with gnumeric chart seems to indicate that its
runtime is roughly log(foursquares(M_p))^2 ...

Regards,

Hermann,