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.)
More information about the Libraries
mailing list