[seqfan] Re: Testing potential squares

[Peter Munn]

Hello Keith,

This thread has been a productive source of methods to help with resource
limits and this type of challenge.

Your particular challenge, if I have understood it, may be appropriate for
the following solution to be the fastest with the resources to hand.

Let L be a lower bound for the numbers being tested, and m be the number
of bits in floor(sqrt(L)). Generate all the squares in the range to be
tested, storing each square n (or its least m bits) in floor((n-L)/2^m)
position of a look-up list, the list elements having been initialised to
-1 for when there is no square within the interval it covers.

Best Regards,

Peter

On Tue, August 21, 2018 1:09 pm, Keith F. Lynch wrote:
> I recently wanted to test a large number of large numbers to see
> if they were squares.  I wanted to do so as quickly as possible.
> The odds of a positive integer around N being square are about
> 1/(2*sqrt(N)).  So if N is around a trillion (10^12), the odds
> are about 1 in 2 million.
>
> The obvious way to test is to take the square root.  But that's slow.
>
> To quickly rule out most non-squares, I created, just once, at the
> beginning of the program, a table of all quadratic residues mod 2^16
> (65536).  Then I tested every potential square by ANDing it with
> 2^16-1 (65535), and looking up the result in that table, both of which
> are very fast.  That rules out nearly 5/6 of all non-squares.  The
> proportions of quadratic residues modulo higher and higher powers of 2
> quickly approach 1/6.  (2^16 already gets 1/5.999268.  See A023105.)

[...]

> If I have one gigabyte to devote to the task, I can instead test my
> prospective square mod 7661478825, a larger record-setting odd number,
> which has about 1/233 residues.  That requires one bit per residue
> to get it to fit in one gigabyte.  If N is my prospective square mod
> 7661478825, I shift N right 3 bits to get the byte to look up in the
> table.  There will be about a 1/29 chance of a hit, i.e. at least one
> residue in the block of 8 containing the correct bit.  Only if there
> is a hit do I check the bit, which I do by ANDing N with 7, and using
> that as the index of which bit in that byte to look at.  So I've ruled
> out all but about 1/1400 non-squares.
>
> I can do better.  [...]

> I'm curious whether anyone can think of a faster way to test large
> numbers for squareness.