isSquare shouldn't use isqrtInt', and its design should be reexamined
isSquare takes an integer square root. This doesn't seem to be necessaryâ€”although truncating the approximate square root ((truncate::Double > Int) . sqrt . fromIntegral) of a number can give a result that's off by one, this does not appear to happen if the number is actually square, so the extra test doesn't accomplish anything. See maaartinus's proof that Double arithmetic is always good enough to find square roots of square Int64s for a detailed discussion.
It also probably makes sense to do some testing to see whether the possible square functions strike the right speed/precision balance. An answer maaartinus gives to this question suggests it may be better to be faster at the expense of precision, because additional or more precise tests may blow away any advantage over floating point square roots. My own answer to that question is a slight simplification that may or may not be slightly faster. Working modulo 64 allows for some absurdly fast and simple bitvector indexing (using rotateL or rotateR and a sign test), but there may well be ways to make some stronger tests fast as well.
Comments (2)


If I read it right, you already do, using some funky RULEs. It would probably be good to expose functions specifically for Int(N) and Word(N). Integer is inherently a mess. Shouldn't the number of tests for Integer be dynamically chosen depending on size, with no fixed upper bound?
 Log in to comment
I should probably write a separate implementation for
Int
andWord
. ForInteger
, I see no shortcuts inintegerSquareRoot
for testing whether it is a square, while forInt
andWord
we can skip the check for the onetoolarge inisSquare
. Also, forInt
andWord
it is indeed quite possible that fewer remainder checks are faster, I wrote and tested theisPossibleSquare
checks for (larger)Integer
s, where computing the floor of the square root is much more expensive, so three or four divisions to reduce the number of square roots to compute pay off. But for the fixedwidth types, I haven't measured, so one additional check after the bitmasking may be better than two. Possibly even none.