testing for perfect squares - my findings on sieving

[William Galway]

If you want to use this algorithm then I suggest you only use the quadratic
residues modulo primes p.  Those values determine all values by using
"quadratic reciprocity".

This technique was used in the paper ON THE BROCARD-RAMANUJAN DIOPHANTINE
EQUATION n!+1=m^2, by Bruce C. Berndt and myself:

  https://faculty.math.illinois.edu/~berndt/articles/galway.pdf

-- Regards, Will (William) Galway


On Tue, Mar 8, 2022 at 5:02 AM Randall Rathbun <
randallrathbun at protonmail.com> wrote:

> Hello all:
>
> Having read up on testing is done for perfect squares, in the
> https://urldefense.com/v3/__https://gmplib.org/manual/Perfect-Square-Algorithm__;!!DZ3fjg!uq8pK5VIeyv5LYjeLCbFqsgJECkISvtPuIbrG6RXkfTZqVjXzmkO-vVfhlkx5FNkOeQ$
> explanation page, I decided to check out how using quadratic residues for
> the integers 1..10000 would fare, when filtering out non-square values.
>
> I had 4,901,796 trials searching for square-sided Heron triangles, thus
> trying to find where the Heron formula gives a perfect square.
>
> (1) Area(a,b,c) = sqrt( (a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c))/4
>
> Due to the data I picked, for sides A = a^2, B = b^2 and C = c^2, there
> was only one answer, at a,b,c = 4473, 4380, 1853 (which is the smallest
> Heron triangle with square sides)
>
> I actually created an array of 10,000 quadratic residues for n=1..10000
> (yes, I know that 1 is trivial, as well as 2, but it made it easy to set up
> the testing program)
>
> I ran the program for 4,901,796 values for (1) but tested each value with
> 10,000 modulo residues, and kept track of how many looked good.
>
> If the value in (1) modulo n == 1, then I added a count to the correct
> n-entry in the counts bin. At the end of the run, the bins with the lower
> counts are more efficient at filtering the potential square into a
> non-square.
>
> What I found out truly surprised me. The choice of 256, and factors of
> 2^48-1 (since I am running a 64-bit system) are not good choices.
>
> Here are the best top 10 performers for filtering non-squares from squares
> and the percentage of non-squares which survived the testing.
>
> 7695 0.003410382643
> 6460 0.003544007135
> 6859 0.003583176452
> 2565 0.003928560062
> 5130 0.003928560062
> 8740 0.004626263516
> 3420 0.004695013828
> 6840 0.004695013828
> 6156 0.004716434548
> 8721 0.004846590923
>
> If a person just picked the best 5 and forced a value to survive all 5
> tests, that percentage drops to
>
> 6.683942 e-13
>
> which is only 1 in 1,496,123,047,598 possible squares slipping though the
> filtering test.
>
> I subsequently have changed my quadratic sieving using the best 5 values
> from above to improve the executation time for (1) I wanted to make things
> easy on
>
> mpz_perfect_square_p
>
> as the callgrind results from my valgrind runs, show that 99%+ time was
> spent on this call
>
> Randall
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
>
> https://urldefense.com/v3/__https://gmplib.org/mailman/listinfo/gmp-discuss__;!!DZ3fjg!uq8pK5VIeyv5LYjeLCbFqsgJECkISvtPuIbrG6RXkfTZqVjXzmkO-vVfhlkx5HGoPmY$
>