speeding up isSquare (Re: Bit shifting limitations)

Henning Thielemann schlepptop at henning-thielemann.de
Sun Jul 13 22:24:59 UTC 2014

```Am 13.07.2014 23:50, schrieb David Feuer:

> the specific thing that I was looking at just now was a Java implementation
> of isSquare that maaartinus wrote on StackOverflow that uses a masked
> shift to index into a (logical) bitvector by the six low-order bits of a
> (logical) integer to see if those bits can be the low-order bits of a
> perfect square.

Taking the six least-significant bits means modulo 64. There are 12
remainders of squares modulo 64:
[0,1,4,9,16,17,25,33,36,41,49,57]

I have run some tests in order to see whether there are divisors with
especially small set of square remainders. A test based on this would
require a full division but you can considerably increase the ratio of
non-square remainders to square-remainders.

Prelude> let sqrRems n = Data.Set.fromList \$ map (\x -> mod (x*x) n) \$
take n [0..]
Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) \$ map (\n -> (n,
Data.Set.size \$ sqrRems n)) [1..64]
(48,8)
Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) \$ map (\n -> (n,
Data.Set.size \$ sqrRems n)) [1..1024]
(1008,64)
Prelude> Data.List.Key.maximum (uncurry (Data.Ratio.%)) \$ map (\n -> (n,
Data.Set.size \$ sqrRems n)) [1..8192]
(7920,288)

That is, if you compute modulo 64, every 5th number will have a square
remainder. In contrast to that, with modulo 7920 only every 27th number
will have a remainder of a square. (Assuming the remainder of the tested
numbers is equally distributed.)

```