speeding up isSquare (Re: Bit shifting limitations)

[Henning Thielemann]

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