[seqfan] Re: Testing potential squares

[Don Reble]

> 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.

> table of all quadratic residues mod 2^16

    If the big number is not zero, the last 2N+3 bits must be 001(00)^N.
    But checking that may be slower than your table lookup.

> having already weeded most non-squares out mod 2^16, ... look for odd
> numbers that have a lower proportion of quadratic residues ...

    It depends on the speeds of square-root and division-remainder.
    It may be good to use the divisor 2^64-1. That remainder is computed
    by summing the 64-bit words of the big number (watch out for
    overflow), and the result is a single word.
    The divisor is 3*5*17*257*641*65537*6700417, so test for square
    remainders modulo those.
    (Use 2^32-1 if your processor is a dinosaur.)

    The remainder of (single-word / single-word-constant) can be
    computed with a multiplication instead of a division: that saves
    time on some processors.

    Division by 2^64-k (for various K values) might also be done
    semi-quickly, and each K provides a new set of moduli.

-- 
Don Reble  djr at nk.ca