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