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 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
- 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
- integerFourthRoot :: Integral a => a -> a
- isFourthPower :: Integral a => a -> Bool
- exactFourthRoot :: 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)
- powMod :: (Integral a, Integral b) => a -> b -> a -> a
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