arithmoi-0.4.0.2: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.

PortabilityNon-portable (GHC extensions)
StabilityProvisional
MaintainerDaniel Fischer <daniel.is.fischer@googlemail.com>
Safe HaskellSafe-Infered

Math.NumberTheory.Powers

Contents

Description

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 -> aSource

Calculate the integer square root of a nonnegative number n, that is, the largest integer r with r*r <= n. Throws an error on negative input.

isSquare :: Integral a => a -> BoolSource

Test whether the argument is a square. After a number is found to be positive, first isPossibleSquare is checked, if it is, the integer square root is calculated.

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

Returns Nothing if the argument is not a square, Just r if r*r == n and r >= 0. Avoids the expensive calculation of the square root if n is recognized as a non-square before, prevents repeated calculation of the square root if only the roots of perfect squares are needed. Checks for negativity and isPossibleSquare.

Cube roots

integerCubeRoot :: Integral a => a -> aSource

Calculate the integer cube root of an integer n, that is the largest integer r such that r^3 <= n. Note that this is not symmetric about 0, for example integerCubeRoot (-2) = (-2) while integerCubeRoot 2 = 1.

isCube :: Integral a => a -> BoolSource

Test whether an integer is a cube.

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

Returns Nothing if the argument is not a cube, Just r if n == r^3.

Fourth roots

integerFourthRoot :: Integral a => a -> aSource

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 -> BoolSource

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

exactFourthRoot :: Integral a => a -> Maybe aSource

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 -> aSource

Calculate an integer root, integerRoot k n computes the (floor of) the k-th root of n, where k must be positive. r = integerRoot k n means r^k <= n < (r+1)^k if that is possible at all. It is impossible if k is even and n < 0, since then r^k >= 0 for all r, then, and if k <= 0, integerRoot raises an error. For k < 5, a specialised version is called which should be more efficient than the general algorithm. However, it is not guaranteed that the rewrite rules for those fire, so if k is known in advance, it is safer to directly call the specialised versions.

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

isKthPower k n checks whether n is a k-th power.

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

exactRoot k n returns Nothing if n is not a k-th power, Just r if n == r^k. If k is divisible by 4, 3 or 2, a residue test is performed to avoid the expensive calculation if it can thus be determined that n is not a k-th power.

isPerfectPower :: Integral a => a -> BoolSource

isPerfectPower n checks whether n == r^k for some k > 1.

highestPower :: Integral a => a -> (a, Int)Source

highestPower n produces the pair (b,k) with the largest exponent k such that n == b^k, except for abs n <= 1, in which case arbitrarily large exponents exist, and by an arbitrary decision (n,3) is returned.

First, by trial division with small primes, the range of possible exponents is reduced (if p^e exactly divides n, then k must be a divisor of e, if several small primes divide n, k must divide the greatest common divisor of their exponents, which mostly will be 1, generally small; if none of the small primes divides n, the range of possible exponents is reduced since the base is necessarily large), if that has not yet determined the result, the remaining factor is examined by trying the divisors of the gcd of the prime exponents if some have been found, otherwise by trying prime exponents recursively.

powerMod :: (Integral a, Bits a) => Integer -> a -> Integer -> IntegerSource

Modular power.

 powerMod base exponent modulus

calculates (base ^ exponent) `mod` modulus by repeated squaring and reduction. If exponent < 0 and base is invertible modulo modulus, (inverse ^ |exponent|) `mod` modulus is calculated. This function does some input checking and sanitation before calling the unsafe worker.