# isSquare shouldn't use isqrtInt', and its design should be re-examined

Issue #8 new
David Feuer
created an issue

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.

I should probably write a separate implementation for `Int` and `Word`. For `Integer`, I see no short-cuts in `integerSquareRoot` for testing whether it is a square, while for `Int` and `Word` we can skip the check for the one-too-large in `isSquare`. Also, for `Int` and `Word` it is indeed quite possible that fewer remainder checks are faster, I wrote and tested the `isPossibleSquare` 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 fixed-width types, I haven't measured, so one additional check after the bit-masking may be better than two. Possibly even none.