Copyright | (c) 2011 Daniel Fischer |
---|---|
License | MIT |
Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Calculating integer roots and determining perfect powers. The algorithms are moderately efficient.
Synopsis
- integerRoot :: (Integral a, Integral b) => b -> a -> a
- exactRoot :: (Integral a, Integral b) => b -> a -> Maybe a
- isKthPower :: (Integral a, Integral b) => b -> a -> Bool
- isPerfectPower :: Integral a => a -> Bool
- highestPower :: Integral a => a -> (a, Word)
- largePFPower :: Integer -> Integer -> (Integer, Word)
Documentation
integerRoot :: (Integral a, Integral b) => b -> a -> a Source #
Calculate an integer root,
computes the (floor of) the integerRoot
k nk
-th
root of n
, where k
must be positive.
r =
means integerRoot
k nr^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
,
raises an error. For integerRoot
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 -> Bool Source #
checks whether isKthPower
k nn
is a k
-th power.
isPerfectPower :: Integral a => a -> Bool Source #
checks whether isPerfectPower
nn == r^k
for some k > 1
.
highestPower :: Integral a => a -> (a, Word) Source #
produces the pair highestPower
n(b,k)
with the largest
exponent k
such that n == b^k
, except for
,
in which case arbitrarily large exponents exist, and by an
arbitrary decision abs
n <= 1(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.
largePFPower :: Integer -> Integer -> (Integer, Word) Source #
produces the pair largePFPower
bd n(b,k)
with the largest
exponent k
such that n == b^k
, where bd > 1
(it is expected
that bd
is much larger, at least 1000
or so), n > bd^2
and n
has no prime factors p <= bd
, skipping the trial division phase
of
when that is a priori known to be superfluous.
It is only present to avoid duplication of work in factorisation
and primality testing, it is not expected to be generally useful.
The assumptions are not checked, if they are not satisfied, wrong
results and wasted work may be the consequence.highestPower