testing for perfect squares - my findings on sieving

[Randall Rathbun]

Hello all:

Having read up on testing is done for perfect squares, in the https://gmplib.org/manual/Perfect-Square-Algorithm 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