Math.NumberTheory.Roots

Calculating integer roots and testing perfect powers.

Square roots

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.

>>> integerSquareRoot 99
9
>>> integerSquareRoot 100
10
>>> integerSquareRoot 101
10

isSquare :: Integral a => a -> Bool

Test whether the argument is a perfect square.

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

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

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

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

Cube roots

integerCubeRoot :: Integral a => a -> a

For a given \( n \) calculate its integer cube root \( \lfloor \sqrt[3]{n} \rfloor \). Note that this is not symmetric about 0.

>>> map integerCubeRoot [7, 8, 9]
[1,2,2]
>>> map integerCubeRoot [-7, -8, -9]
[-2,-2,-3]

isCube :: Integral a => a -> Bool

Test whether the argument is a perfect cube.

>>> map isCube [-9, -8, -7, 7, 8, 9]
[False,True,False,False,True,False]

exactCubeRoot :: Integral a => a -> Maybe a

Calculate the exact integer cube root if it exists, otherwise return Nothing.

>>> map exactCubeRoot [-9, -8, -7, 7, 8, 9]
[Nothing,Just (-2),Nothing,Nothing,Just 2,Nothing]

k-th roots

integerRoot :: (Integral a, Integral b) => b -> a -> a

For a positive power \( k \) and a given \( n \) return the integer \( k \)-th root \( \lfloor \sqrt[k]{n} \rfloor \). Throw an error if \( k \le 0 \) or if \( n \le 0 \) and \( k \) is even.

>>> integerRoot 6 65
2
>>> integerRoot 5 243
3
>>> integerRoot 4 624
4
>>> integerRoot 3 (-124)
-5
>>> integerRoot 1 5
5

isKthPower :: (Integral a, Integral b) => b -> a -> Bool

For a positive exponent \( k \) test whether the second argument is a perfect \( k \)-th power.

>>> map (uncurry isKthPower) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
[False,True,False,False,True]

exactRoot :: (Integral a, Integral b) => b -> a -> Maybe a

For a positive exponent \( k \) calculate the exact integer \( k \)-th root of the second argument if it exists, otherwise return Nothing.

>>> map (uncurry exactRoot) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
[Nothing,Just 3,Nothing,Nothing,Just 5]

Perfect powers

isPerfectPower :: Integral a => a -> Bool

Test whether the argument is a non-trivial perfect power (e. g., square, cube, etc.).

>>> map isPerfectPower [0..10]
[True,True,False,False,True,False,False,False,True,True,False]
>>> map isPerfectPower [-10..0]
[False,False,True,False,False,False,False,False,False,True,True]

highestPower :: Integral a => a -> (a, Word)

For \( n \not\in \{ -1, 0, 1 \} \) find the largest exponent \( k \) for which an exact integer \( k \)-th root \( r \) exists. Return \( (r, k) \).

For \( n \in \{ -1, 0, 1 \} \) arbitrarily large exponents exist; by arbitrary convention highestPower returns \( (n, 3) \).

>>> map highestPower [0..10]
[(0,3),(1,3),(2,1),(3,1),(2,2),(5,1),(6,1),(7,1),(2,3),(3,2),(10,1)]
>>> map highestPower [-10..0]
[(-10,1),(-9,1),(-2,3),(-7,1),(-6,1),(-5,1),(-4,1),(-3,1),(-2,1),(-1,3),(0,3)]