testing for perfect squares - my findings on sieving

[Marco Bodrato]

Ciao,

Il 2022-03-08 08:14 Randall Rathbun ha scritto:
> 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.

> 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

> 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

You are multiplying as if the 5 filters were independent.
Did you check if they are?

7695 = 3*2565
5130 = 2*2565

I suspect that any number passing the 7695-filter passes also both the 
5130-filter and the 2565-filter.

> 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

If the numbers you are testing have some special structure, it may be a 
good idea to check them somehow before passing them to the general 
purpose library.

For general random numbers, I'd expect to see 12% of non-square numbers 
passing a modulo 7695 square residue test, versus 17% for 256... with 
the latter being much faster! and with much smaller tables.

Let us know if, with your quadratic sieving, the resulting tests are 
much faster.

Ĝis,
m

-- 
http://bodrato.it/papers/