factory- Rational arithmetic in an irrational world.

Safe HaskellNone




Dr. Alistair Ward
  • https://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; https://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 Source #

Defines the methods expected of a factorisation-algorithm.

Minimal complete definition



primeFactors :: (NFData base, Integral base) => algorithm -> base -> Factors base Int Source #


Algorithmic Algorithm Source # 


primeFactors :: (NFData base, Integral base) => Algorithm -> base -> Factors base Int Source #


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 (x div 2) for 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.
  • N.B.: 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 #

powerSmoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] Source #

regularNumbers :: (Algorithmic algorithm, Integral base) => algorithm -> [base] Source #

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 #

omega :: (Algorithmic algorithm, Integral i) => algorithm -> [i] Source #

squareFree :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i] Source #