integer-roots-1.0.4.0: Integer roots and perfect powers

Copyright | (c) 2011 Daniel Fischer 2016-2020 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell2010

Math.NumberTheory.Roots

Contents

- Square roots
- Cube roots
- k-th roots
- Perfect powers

Description

Calculating integer roots and testing perfect powers.

Synopsis

- integerSquareRoot :: Integral a => a -> a
- isSquare :: Integral a => a -> Bool
- exactSquareRoot :: Integral a => a -> Maybe a
- integerCubeRoot :: Integral a => a -> a
- isCube :: Integral a => a -> Bool
- exactCubeRoot :: Integral a => a -> Maybe a
- integerRoot :: (Integral a, Integral b) => b -> a -> a
- isKthPower :: (Integral a, Integral b) => b -> a -> Bool
- exactRoot :: (Integral a, Integral b) => b -> a -> Maybe a
- isPerfectPower :: Integral a => a -> Bool
- highestPower :: Integral a => a -> (a, Word)

# Square roots

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

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

Test whether the argument is a perfect square.

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

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

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

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

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

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

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

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

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

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

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