| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Factory.Math.PrimeFactorisation
Contents
Description
AUTHOR- Dr. Alistair Ward
DESCRIPTION
- http://en.wikipedia.org/wiki/Integer_factorization.
- Exports a common interface to permit decomposition of positive integers, into the unique combination of prime-factors known to exist according to the Fundamental Theorem of Arithmetic; http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.
- Leveraging this abstract capability, it derives the smoothness, power-smoothness, omega-numbers and square-free integers.
- Filters the list of regular-numbers from the list of smoothness.
- CAVEAT: to avoid wasting time, it may be advantageous to check Factory.Math.Primality.isPrime first.
- class Algorithmic algorithm where
- primeFactors :: (NFData base, Integral base) => algorithm -> base -> Factors base Int
- maxBoundPrimeFactor :: Integral i => i -> i
- smoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base]
- powerSmoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base]
- regularNumbers :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base]
- primePowerTotient :: (Integral base, Integral exponent) => Exponential base exponent -> base
- eulersTotient :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> i
- omega :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i]
- squareFree :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i]
Type-classes
class Algorithmic algorithm where Source
Defines the methods expected of a factorisation-algorithm.
Methods
Instances
Functions
maxBoundPrimeFactor :: Integral i => i -> i Source
- The upper limit for a prime to be considered as a candidate factor of the specified number.
- One might naively think that this limit is
(xfor an even number, but though a prime-factor greater than the square-root of the number can exist, its smaller cofactor decomposes to a prime which must be less than the square-root.div2) - NB: rather then using
(primeFactor <= sqrt numerator)to filter the candidate prime-factors of a given numerator, one can alternatively use(numerator >= primeFactor ^ 2)to filter what can potentially be factored by a given prime-factor. - CAVEAT: suffers from rounding-errors, though no consequence has been witnessed.
smoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source
- A constant, zero-indexed, conceptually infinite, list, of the smoothness of all positive integers.
- http://en.wikipedia.org/wiki/Smooth_number.
- http://mathworld.wolfram.com/SmoothNumber.html.
powerSmoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source
- A constant, zero-indexed, conceptually infinite, list of the power-smoothness of all positive integers.
- http://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers.
regularNumbers :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source
- Filters
smoothness, to derive the constant list of Hamming-numbers. - http://en.wikipedia.org/wiki/Regular_number.
primePowerTotient :: (Integral base, Integral exponent) => Exponential base exponent -> base Source
- Euler's Totient for a power of a prime-number.
- By Olofsson;
(phi(n^k) = n^(k - 1) * phi(n))and since(phi(prime) = prime - 1) - CAVEAT: checks neither the primality nor the bounds of the specified value; therefore for internal use only.
eulersTotient :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> i Source
- The number of coprimes less than or equal to the specified positive integer.
- http://en.wikipedia.org/wiki/Euler%27s_totient_function.
- http://mathworld.wolfram.com/TotientFunction.html.
- AKA EulerPhi.
omega :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i] Source
- A constant, zero-indexed, conceptually infinite, list of the small omega numbers (i.e. the number of distinct prime factors); cf. big omega.
- http://oeis.org/wiki/Omega%28n%29,_number_of_distinct_primes_dividing_n.
- http://mathworld.wolfram.com/DistinctPrimeFactors.html
- http://planetmath.org/encyclopedia/NumberOfDistinctPrimeFactorsFunction.html.
squareFree :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i] Source
- A constant, conceptually infinite, list of the square-free numbers, i.e. those which aren't divisible by any perfect square.
- http://en.wikipedia.org/wiki/Square-free_integer.