Portability | Non-portable (GHC extensions) |
---|---|
Stability | Provisional |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Functions dealing with squares. Efficient calculation of integer square roots and efficient testing for squareness.
- integerSquareRoot :: Integral a => a -> a
- integerSquareRoot' :: Integral a => a -> a
- exactSquareRoot :: Integral a => a -> Maybe a
- isSquare :: Integral a => a -> Bool
- isSquare' :: Integral a => a -> Bool
- isPossibleSquare :: Integral a => a -> Bool
- isPossibleSquare2 :: Integral a => a -> Bool
Square root calculation
integerSquareRoot :: Integral a => a -> aSource
Calculate the integer square root of a nonnegative number n
,
that is, the largest integer r
with r*r <= n
.
Throws an error on negative input.
integerSquareRoot' :: Integral a => a -> aSource
Calculate the integer square root of a nonnegative number n
,
that is, the largest integer r
with r*r <= n
.
The precondition n >= 0
is not checked.
exactSquareRoot :: Integral a => a -> Maybe aSource
Returns Nothing
if the argument is not a square,
if Just
rr*r == n
and r >= 0
. Avoids the expensive calculation
of the square root if n
is recognized as a non-square
before, prevents repeated calculation of the square root
if only the roots of perfect squares are needed.
Checks for negativity and isPossibleSquare
.
Tests for squares
isSquare :: Integral a => a -> BoolSource
Test whether the argument is a square.
After a number is found to be positive, first isPossibleSquare
is checked, if it is, the integer square root is calculated.
isSquare' :: Integral a => a -> BoolSource
Test whether the input (a nonnegative number) n
is a square.
The same as isSquare
, but without the negativity test.
Faster if many known positive numbers are tested.
The precondition n >= 0
is not tested, passing negative
arguments may cause any kind of havoc.
isPossibleSquare :: Integral a => a -> BoolSource
Test whether a non-negative number may be a square. Non-negativity is not checked, passing negative arguments may cause any kind of havoc.
First the remainder modulo 256 is checked (that can be calculated easily without division and eliminates about 82% of all numbers). After that, the remainders modulo 9, 25, 7, 11 and 13 are tested to eliminate altogether about 99.436% of all numbers.
This is the test used by exactSquareRoot
. For large numbers,
the slower but more discriminating test isPossibleSqure2
is
faster.
isPossibleSquare2 :: Integral a => a -> BoolSource
Test whether a non-negative number may be a square. Non-negativity is not checked, passing negative arguments may cause any kind of havoc.
First the remainder modulo 256 is checked (that can be calculated easily without division and eliminates about 82% of all numbers). After that, the remainders modulo several small primes are tested to eliminate altogether about 99.98954% of all numbers.
For smallish to medium sized numbers, this hardly performs better
than isPossibleSquare
, which uses smaller arrays, but for large
numbers, where calculating the square root becomes more expensive,
it is much faster (if the vast majority of tested numbers aren't squares).