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.

Comments (2)

  1. dafis repo owner

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

  2. David Feuer reporter

    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?

  3. Log in to comment