arithmoi-0.11.0.0: Efficient basic number-theoretic functions.

Math.NumberTheory.Powers

Description

Deprecated: Use Math.NumberTheory.Roots or Math.NumberTheory.Powers.Modular

Description: Deprecated

Calculating integer roots, modular powers and related things. This module reexports the most needed functions from the implementation modules. The implementation modules provide some additional functions, in particular some unsafe functions which omit some tests for performance reasons.

Synopsis

# Integer Roots

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


## Fourth roots

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

Calculate the integer fourth root of a nonnegative number, that is, the largest integer r with r^4 <= n. Throws an error on negaitve input.

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

Test whether an integer is a fourth power. First nonnegativity is checked, then the unchecked test is called.

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

Returns Nothing if n is not a fourth power, Just r if n == r^4 and r >= 0.

## General 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]


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


# Modular powers

powMod :: (Integral a, Integral b) => a -> b -> a -> a Source #

powMod b e m computes (b^e) mod m in effective way. An exponent e must be non-negative, a modulo m must be positive. Otherwise the behaviour of powMod is undefined.

>>> powMod 2 3 5
3
>>> powMod 3 12345678901234567890 1001
1


See also powMod and powSomeMod.

For finite numeric types (Int, Word, etc.) modulo m should be such that m^2 does not overflow, otherwise the behaviour is undefined. If you need both to fit into machine word and to handle large moduli, take a look at powModInt and powModWord.

>>> powMod 3 101 (2^60-1 :: Integer)
1018105167100379328 -- correct
>>> powMod 3 101 (2^60-1 :: Int)
1115647832265427613 -- incorrect due to overflow
>>> powModInt 3 101 (2^60-1 :: Int)
1018105167100379328 -- correct