Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Safe Haskell | None |

Language | Haskell2010 |

Deprecated: Use Math.NumberTheory.Roots

Description: Deprecated

Functions dealing with squares. Efficient calculation of integer square roots and efficient testing for squareness.

## Synopsis

- integerSquareRoot :: Integral a => a -> a
- integerSquareRoot' :: Integral a => a -> a
- integerSquareRootRem :: Integral a => a -> (a, a)
- integerSquareRootRem' :: Integral a => 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 -> a #

For a non-negative input \( n \) calculate its integer square root \( \lfloor \sqrt{n} \rfloor \). Throw an error on negative input.

`>>>`

9`integerSquareRoot 99`

`>>>`

10`integerSquareRoot 100`

`>>>`

10`integerSquareRoot 101`

integerSquareRoot' :: Integral a => a -> a Source #

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.

integerSquareRootRem :: Integral a => a -> (a, a) Source #

Calculate the integer square root of a nonnegative number as well as
the difference of that number with the square of that root, that is if
`(s,r) = integerSquareRootRem n`

then `s^2 <= n == s^2+r < (s+1)^2`

.

integerSquareRootRem' :: Integral a => a -> (a, a) Source #

Calculate the integer square root of a nonnegative number as well as
the difference of that number with the square of that root, that is if
`(s,r) = integerSquareRootRem' n`

then `s^2 <= n == s^2+r < (s+1)^2`

.
The precondition `n >= 0`

is not checked.

exactSquareRoot :: Integral a => a -> Maybe a #

Calculate the exact integer square root if it exists,
otherwise return `Nothing`

.

`>>>`

[Nothing,Nothing,Just 10,Nothing]`map exactSquareRoot [-100, 99, 100, 101]`

# Tests for squares

isSquare :: Integral a => a -> Bool #

Test whether the argument is a perfect square.

`>>>`

[False,False,True,False]`map isSquare [-100, 99, 100, 101]`

isSquare' :: Integral a => a -> Bool Source #

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 -> Bool Source #

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 `isPossibleSquare2`

is
faster.

isPossibleSquare2 :: Integral a => a -> Bool Source #

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