-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Rational arithmetic in an irrational world. -- -- A library of number-theory functions, for; factorials, square-roots, -- Pi and primes. @package factory @version 0.2.0.5 -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Facilitates representation of -- Integral values in alternative Integral bases.

module Factory.Math.Radix -- |

http://mathworld.wolfram.com/DigitSum.html.
http://en.wikipedia.org/wiki/Digit_sum.

digitSum :: (Ix decimal, Integral base, Integral decimal, Show base, Show decimal) => base -> decimal -> decimal -- | http://en.wikipedia.org/wiki/Digital_root. digitalRoot :: (Ix decimal, Integral decimal, Show decimal) => decimal -> decimal -- |

Convert the String-representation of a number in the -- specified base, to a decimal integer.
Both negative numbers and negative bases are permissible.

fromBase :: (Integral base, Integral decimal, Read decimal, Show base) => base -> String -> decimal -- |

Convert the specified integral decimal quantity, to an alternative -- base, and represent the result as a String.
Both negative decimals and negative bases are permissible.
The conversion to Char can only succeed where printable and -- intelligible characters exist to represent all digits in the chosen -- base; which in practice means (-36 <= base <= 36).

toBase :: (Ix decimal, Integral base, Integral decimal, Show base, Show decimal) => base -> decimal -> String -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Exports a common interface for -- implementations of prime-number generators.

module Factory.Math.Primes -- | Defines the methods expected of a prime-number generator. class Algorithmic algorithm primes :: (Algorithmic algorithm, NFData i, Ix i, Integral i) => algorithm -> [i] -- |

Returns the constant list, defining the Primorial.
http://en.wikipedia.org/wiki/Primorial.
http://mathworld.wolfram.com/Primorial.html.

primorial :: (Algorithmic algorithm, NFData i, Ix i, Integral i) => algorithm -> [i] -- |

Returns the constant ordered infinite list of Mersenne -- numbers.
Only the subset composed from a prime exponent is returned; which -- is a strict superset of the Mersenne Primes.
http://en.wikipedia.org/wiki/Mersenne_prime.
http://mathworld.wolfram.com/MersenneNumber.html

mersenneNumbers :: (Algorithmic algorithm, Integral i) => algorithm -> [i] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Provides an alternative algorithm for -- the summation of rational numbers.

module Factory.Math.Summation -- |

Sums a list of numbers of arbitrary type.
Sparks the summation of (list-length / chunk-size) chunks -- from the list, each of the specified size (thought the last chunk may -- be smaller), then recursively sums the list of results from each -- spark.
CAVEAT: unless the numbers are large, Rational (requiring -- cross-multiplication), or the list long, sum is too -- light-weight for sparking to be productive, therefore it is more -- likely to be the parallelised deep evaluation of list-elements -- which saves time.

sum' :: (Num n, NFData n) => Int -> [n] -> n -- |

Sums a list of rational type numbers.
CAVEAT: though faster than sum, this algorithm has poor -- space-complexity, making it unsuitable for unrestricted use.

sumR' :: Integral i => [Ratio i] -> Ratio i -- |

Sums a list of rational numbers.
Sparks the summation of (list-length / chunk-length) -- chunks from the list, each of the specified size (thought the last -- chunk may be smaller), then recursively sums the list of results from -- each spark.
CAVEAT: memory-use is proportional to chunk-size.

sumR :: (Integral i, NFData i) => Int -> [Ratio i] -> Ratio i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines a -- Bailey-Borwein-Plouffe formula; -- http://mathworld.wolfram.com/PiFormulas.html

module Factory.Math.Implementations.Pi.BBP.Series -- | Defines a series corresponding to a specific BBP-formula. data Series MkSeries :: [Integer] -> (Int -> [Integer]) -> Rational -> Integer -> Series -- | The constant numerators from which each term in the series is -- composed. numerators :: Series -> [Integer] -- | Generates the term-dependent denominators from which each term in the -- series is composed. getDenominators :: Series -> Int -> [Integer] -- | The ratio by which the sum to infinity of the series, must be scaled -- to result in Pi. seriesScalingFactor :: Series -> Rational -- | The geometric ratio, by which successive terms are scaled. base :: Series -> Integer -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines Bellard's -- nega-base-2^10 BBP-formula; -- http://en.wikipedia.org/wiki/Bellard%27s_formula

module Factory.Math.Implementations.Pi.BBP.Bellard -- | Defines the parameters of this specific series. series :: Series -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines a specific base-2^16 -- BBP-formula; -- http://mathworld.wolfram.com/PiFormulas.html

module Factory.Math.Implementations.Pi.BBP.Base65536 -- | Defines the parameters of this specific series. series :: Series -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Exports functions involving integral -- powers.

module Factory.Math.Power -- | Mainly for convenience. square :: Num n => n -> n -- |

Iteratively generate sequential squares, from the specified -- initial value, based on the fact that (x + 1)^2 = x^2 + 2 * x + -- 1.
The initial value doesn't need to be either positive or -- integral.

squaresFrom :: (Enum n, Num n) => n -> [(n, n)] -- | Just for convenience. cube :: Num n => n -> n -- | Just for convenience. cubeRoot :: Double -> Double -- |

Raise an arbitrary number to the specified positive integral -- power, using modular arithmetic.
Implements exponentiation as a sequence of either squares -- or multiplications by the base; -- http://en.wikipedia.org/wiki/Exponentiation_by_squaring.
http://en.wikipedia.org/wiki/Modular_exponentiation.

raiseModulo :: (Integral i, Integral power, Show power) => i -> power -> i -> i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Exports functions related to -- perfect powers.

module Factory.Math.PerfectPower -- |

Returns (Just . sqrt) if the specified integer is a -- square number (AKA perfect square).
http://en.wikipedia.org/wiki/Square_number.
http://mathworld.wolfram.com/SquareNumber.html.
(Math.Power.square . sqrt) is expensive, so the modulus -- of the operand is tested first, in an attempt to prove it isn't a -- perfect square. The set of tests, and the valid moduli within -- each test, are ordered to maximize the rate of failure-detection.

maybeSquareNumber :: Integral i => i -> Maybe i -- |

An integer (> 1) which can be expressed as an integral -- power (> 1) of a smaller natural number.
CAVEAT: zero and one are normally excluded from this -- set.
http://en.wikipedia.org/wiki/Perfect_power.
http://mathworld.wolfram.com/PerfectPower.html.
A generalisation of the concept of perfect squares, in -- which only the exponent '2' is significant.

isPerfectPower :: Integral i => i -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Exports a common interface for primality-implementations.
Provides utilities for these implementations.

module Factory.Math.Primality -- | Defines the methods expected of a primality-testing algorithm. class Algorithmic algorithm isPrime :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> Bool -- | An ordered list of the Carmichael numbers; -- http://en.wikipedia.org/wiki/Carmichael_number. carmichaelNumbers :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> [i] -- | True if the two specified integers are relatively prime, -- i.e. if they share no common positive factors except one. -- --

1 and -1 are the only numbers which are -- coprime to themself.
http://en.wikipedia.org/wiki/Coprime.
http://mathworld.wolfram.com/RelativelyPrime.html.

areCoprime :: Integral i => i -> i -> Bool -- |

Tests Fermat's Little Theorem for all applicable values, as -- a probabilistic primality-test.
http://en.wikipedia.org/wiki/Fermat%27s_little_theorem.
http://en.wikipedia.org/wiki/Fermat_primality_test.
http://en.wikipedia.org/wiki/Fermat_pseudoprime.
CAVEAT: this primality-test fails for the Carmichael -- numbers.
TODO: confirm that all values must be tested.

isFermatWitness :: (Integral i, Show i) => i -> Bool -- |

A Carmichael number is an odd composite -- number which satisfies Fermat's little theorem.
http://en.wikipedia.org/wiki/Carmichael_number.
http://mathworld.wolfram.com/CarmichaelNumber.html.

isCarmichaelNumber :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Generates the constant, conceptally -- infinite, list of prime-numbers, using Turner's Sieve; -- http://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division.

module Factory.Math.Implementations.Primes.TurnersSieve -- |

For each prime, the infinite list of candidates greater -- than its square, is filtered for indivisibility; -- http://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division.
CAVEAT: though one can easily add a PrimeWheel, it proved -- counterproductive.

turnersSieve :: Integral prime => [prime] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Provides various -- hyperoperations; -- http://en.wikipedia.org/wiki/Hyperoperation.

module Factory.Math.Hyperoperation -- |

Merely to enhance self-documentation.
CAVEAT: whilst it may appear that Base could be -- non-Integral, the recursive definition for -- hyper-exponents above tetration, prevents this.

type Base = Integer -- |

Merely to enhance self-documentation.
CAVEAT: whilst Base and HyperExponent can be -- independent types for both exponentiation and tetration, -- they interact for other hyper-exponents.

type HyperExponent = Base succession :: Int addition :: Int multiplication :: Int exponentiation :: Int tetration :: Int pentation :: Int hexation :: Int -- | The hyperoperation-sequence; -- http://en.wikipedia.org/wiki/Hyperoperation. hyperoperation :: (Integral rank, Show rank) => rank -> Base -> HyperExponent -> Base -- | The Ackermann-Peter-function; -- http://en.wikipedia.org/wiki/Ackermann_function#Ackermann_numbers. ackermannPeter :: (Integral rank, Show rank) => rank -> HyperExponent -> Base -- |

Returns the power-tower of the specified base; -- http://mathworld.wolfram.com/PowerTower.html.
A synonym for tetration; -- http://en.wikipedia.org/wiki/Tetration, -- http://www.tetration.org/Fractals/Atlas/index.html.

powerTower :: (Integral base, Integral hyperExponent, Show base) => base -> hyperExponent -> base -- | True if hyperoperation base hyperExponent has the same value -- for each specified rank. areCoincidental :: (Integral rank, Show rank) => Base -> HyperExponent -> [rank] -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION -- http://en.wikipedia.org/wiki/Fibonacci_number.

module Factory.Math.Fibonacci -- | A constant ordered list of the Fibonacci-numbers. fibonacci :: Integral i => [i] -- |

The subset of fibonacci, indexed by a -- prime-number.
http://primes.utm.edu/glossary/page.php?sort=FibonacciPrime.

primeIndexedFibonacci :: Integral i => [i] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Whilst this particular function is the subject of many -- introductory examples to Haskell, the simple algorithms appropriate -- for that forum, leave a large margin for performance-improvement. This -- module provides the interface for alternative algorithms.
http://mathworld.wolfram.com/Factorial.html.

module Factory.Math.Factorial -- | Defines the methods expected of a factorial-algorithm. class Algorithmic algorithm factorial :: (Algorithmic algorithm, Integral i, Show i) => algorithm -> i -> i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the unit with which precision -- is measured, and operations on it.

module Factory.Math.Precision -- | The order of convergence; -- http://en.wikipedia.org/wiki/Rate_of_convergence. type ConvergenceOrder = Int -- | The rate of convergence; -- http://en.wikipedia.org/wiki/Rate_of_convergence. type ConvergenceRate = Double -- | A number of decimal digits. type DecimalDigits = Int -- | Linear convergence-rate; which may be qualified by the rate -- of convergence. linearConvergence :: ConvergenceOrder -- | Quadratic convergence-rate. quadraticConvergence :: ConvergenceOrder -- | Cubic convergence-rate. cubicConvergence :: ConvergenceOrder -- | Quartic convergence-rate. quarticConvergence :: ConvergenceOrder -- | The predicted number of iterations, required to achieve a specific -- accuracy, at a given order of convergence. getIterationsRequired :: Integral i => ConvergenceOrder -> DecimalDigits -> DecimalDigits -> i -- |

The predicted number of terms which must be extracted from a -- series, if it is to converge to the required accuracy, at the -- specified linear convergence-rate.
The convergence-rate of a series, is the error in the -- series after summation of (n+1)th terms, divided by the error -- after only n terms, as the latter tends to infinity. As such, -- for a convergent series (in which the error get smaller with -- successive terms), it's value lies in the range 0 .. 1.
http://en.wikipedia.org/wiki/Rate_of_convergence.

getTermsRequired :: Integral i => ConvergenceRate -> DecimalDigits -> i -- | Promotes the specified number, by a number of DecimalDigits. promote :: Num n => n -> DecimalDigits -> n -- |

Reduces a Rational to the minimal form required for the -- specified number of fractional decimal places; irrespective of -- the number of integral decimal places.
A Rational approximation to an irrational number, may be -- very long, and provide an unknown excess precision. Whilst this -- doesn't sound harmful, it costs in performance and memory-requirement, -- and being unpredictable isn't actually useful.

simplify :: RealFrac operand => DecimalDigits -> operand -> Rational -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Exports a common interface for square-root -- implementations.
Provides utilities for these implementations.

module Factory.Math.SquareRoot -- | Defines the methods expected of a square-root algorithm. class Algorithmic algorithm where squareRoot algorithm decimalDigits operand = squareRootFrom algorithm (getEstimate operand) decimalDigits operand squareRootFrom :: (Algorithmic algorithm, Real operand, Show operand) => algorithm -> Estimate -> DecimalDigits -> operand -> Result squareRoot :: (Algorithmic algorithm, Real operand, Show operand) => algorithm -> DecimalDigits -> operand -> Result -- | The interface required to iterate, from an estimate of the required -- value, to the next approximation. class Iterator algorithm step :: (Iterator algorithm, Real operand) => algorithm -> operand -> Result -> Result convergenceOrder :: Iterator algorithm => algorithm -> ConvergenceOrder -- | The result-type; actually, only the concrete return-type of -- simplify, stops it being a polymorphic instance of -- Fractional. type Result = Rational -- | Contains an estimate for the square-root of a value, and its -- accuracy. type Estimate = (Result, DecimalDigits) -- |

For a given value and an estimate of its square-root, -- returns the number of decimals digits to which the square-root -- is accurate; including the integral digits.
CAVEAT: the result returned for an exact match has been -- bodged.

getAccuracy :: Real operand => operand -> Result -> DecimalDigits -- |

The signed difference between the square of an estimate for -- the square-root of a value, and that value.
Positive when the estimate is too low.
CAVEAT: the magnitude is twice the error in the -- square-root.

getDiscrepancy :: Real operand => operand -> Result -> Result -- | Uses Double-precision floating-point arithmetic, to obtain an -- initial estimate for the square-root, and its accuracy. getEstimate :: (Real operand, Show operand) => operand -> Estimate -- | True if the specified estimate for the square-root, is precise. isPrecise :: Real operand => operand -> Result -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the classes of -- Pi-algorithm which have been implemented.

module Factory.Math.Pi -- |

Defines the methods expected of a Pi-algorithm.
Most of the implementations naturally return a Rational, -- but the spigot-algorithms naturally produce a [Int]; though -- representing Pi as a big integer with the decimal point removed -- is clearly incorrect.
Since representing Pi as either a Rational or -- promoted to an Integer, is inconvenient, an alternative decimal -- String-representation is provided.

class Algorithmic algorithm where openI _ 1 = 3 openI algorithm decimalDigits | decimalDigits <= 0 = error $ "Factory.Math.Pi.openI:\tinsufficient decimalDigits=" ++ show decimalDigits | otherwise = round . promote (openR algorithm decimalDigits) $ pred decimalDigits openS _ 1 = "3" openS algorithm decimalDigits | decimalDigits <= 0 = "" | decimalDigits <= 16 = take (succ decimalDigits) $ show (pi :: Double) | otherwise = "3." ++ tail (show $ openI algorithm decimalDigits) openR :: Algorithmic algorithm => algorithm -> DecimalDigits -> Rational openI :: Algorithmic algorithm => algorithm -> DecimalDigits -> Integer openS :: Algorithmic algorithm => algorithm -> DecimalDigits -> String -- | Categorises the various algorithms. data Category agm bbp borwein ramanujan spigot -- | Algorithms based on the Arithmetic-geometric Mean. AGM :: agm -> Category agm bbp borwein ramanujan spigot -- | -- http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula. BBP :: bbp -> Category agm bbp borwein ramanujan spigot -- | http://en.wikipedia.org/wiki/Borwein%27s_algorithm. Borwein :: borwein -> Category agm bbp borwein ramanujan spigot -- | http://www.pi314.net/eng/ramanujan.php. Ramanujan :: ramanujan -> Category agm bbp borwein ramanujan spigot -- | Algorithms from which the digits of Pi slowly drip, one by one. Spigot :: spigot -> Category agm bbp borwein ramanujan spigot instance (Eq agm, Eq bbp, Eq borwein, Eq ramanujan, Eq spigot) => Eq (Category agm bbp borwein ramanujan spigot) instance (Read agm, Read bbp, Read borwein, Read ramanujan, Read spigot) => Read (Category agm bbp borwein ramanujan spigot) instance (Show agm, Show bbp, Show borwein, Show ramanujan, Show spigot) => Show (Category agm bbp borwein ramanujan spigot) instance (Algorithmic agm, Algorithmic bbp, Algorithmic borwein, Algorithmic ramanujan, Algorithmic spigot) => Algorithmic (Category agm bbp borwein ramanujan spigot) instance (Defaultable agm, Defaultable bbp, Defaultable borwein, Defaultable ramanujan, Defaultable spigot) => Defaultable (Category agm bbp borwein ramanujan spigot) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Implements a Bailey-Borwein-Plouffe formula; -- http://mathworld.wolfram.com/PiFormulas.html
Surprisingly, because of the huge size of the Rational -- quantities, it is a single call to -- Factory.Math.Summation.sum', rather than the calculation of -- the many terms in the series, which is the -- performance-bottleneck.

module Factory.Math.Implementations.Pi.BBP.Implementation -- | Returns Pi, accurate to the specified number of decimal digits. openR :: Series -> DecimalDigits -> Rational -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the set of -- Bailey-Borwein-Plouffe-type formulae which have been -- implemented.

module Factory.Math.Implementations.Pi.BBP.Algorithm -- | Defines those BBP-type series which have been implemented. data Algorithm -- | A base-2^16 version of the formula. Base65536 :: Algorithm -- | A nega-base 2^10 version of the formula. Bellard :: Algorithm instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines a -- http://en.wikipedia.org/wiki/Srinivasa_Borwein-type series for -- Pi.

module Factory.Math.Implementations.Pi.Borwein.Series -- | Defines a series corresponding to a specific Borwein-formula. data Series squareRootAlgorithm factorialAlgorithm MkSeries :: (squareRootAlgorithm -> factorialAlgorithm -> DecimalDigits -> (Rational, [Rational])) -> ConvergenceRate -> Series squareRootAlgorithm factorialAlgorithm terms :: Series squareRootAlgorithm factorialAlgorithm -> squareRootAlgorithm -> factorialAlgorithm -> DecimalDigits -> (Rational, [Rational]) -- | The expected number of digits of Pi, per term in the series. convergenceRate :: Series squareRootAlgorithm factorialAlgorithm -> ConvergenceRate -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines Borwein series for -- Pi; -- http://en.wikipedia.org/wiki/Borwein%27s_algorithm

module Factory.Math.Implementations.Pi.Borwein.Implementation -- | Returns Pi, accurate to the specified number of decimal digits. openR :: Series squareRootAlgorithm factorialAlgorithm -> squareRootAlgorithm -> factorialAlgorithm -> DecimalDigits -> Rational -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines a -- http://en.wikipedia.org/wiki/Srinivasa_Ramanujan-type series -- for Pi.

module Factory.Math.Implementations.Pi.Ramanujan.Series -- | Defines a series corresponding to a specific Ramanujan-formula. data Series squareRootAlgorithm factorialAlgorithm MkSeries :: (factorialAlgorithm -> [Rational]) -> (squareRootAlgorithm -> DecimalDigits -> Rational) -> ConvergenceRate -> Series squareRootAlgorithm factorialAlgorithm -- | The sequence of terms, the sum to infinity of which defines the -- series. terms :: Series squareRootAlgorithm factorialAlgorithm -> factorialAlgorithm -> [Rational] -- | The ratio by which the sum to infinity of the sequence, must be scaled -- to result in Pi. getSeriesScalingFactor :: Series squareRootAlgorithm factorialAlgorithm -> squareRootAlgorithm -> DecimalDigits -> Rational -- | The expected number of digits of Pi, per term in the series. convergenceRate :: Series squareRootAlgorithm factorialAlgorithm -> ConvergenceRate -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Implements a Ramanujan-type -- series for Pi; -- http://en.wikipedia.org/wiki/Srinivasa_Ramanujan.

module Factory.Math.Implementations.Pi.Ramanujan.Implementation -- | Returns Pi, accurate to the specified number of decimal digits. openR :: Series squareRootAlgorithm factorialAlgorithm -> squareRootAlgorithm -> factorialAlgorithm -> DecimalDigits -> Rational -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the parameters of a series -- used in a Spigot-table to generate Pi.

module Factory.Math.Implementations.Pi.Spigot.Series -- |

Defines a series composed from a sum of terms, each one of which -- is the product of a coefficient and a base.
The coefficents and bases of the series are described in Horner -- form; Pi = c1 + (b1 * (c2 + b2 * (c3 + b3 * -- (...)))).

data Series i MkSeries :: [i] -> [i] -> [i] -> (DecimalDigits -> Int) -> Series i coefficients :: Series i -> [i] baseNumerators :: Series i -> [i] baseDenominators :: Series i -> [i] -- | The width of the spigot-table, required to accurately generate the -- requested number of digits. nTerms :: Series i -> DecimalDigits -> Int -- | Combines baseNumerators and baseDenominators, and as a -- side-effect, expresses the ratio in lowest terms. bases :: Integral i => Series i -> [Ratio i] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the Gosper series; -- http://www.pi314.net/eng/goutte.php

module Factory.Math.Implementations.Pi.Spigot.Gosper -- | Defines a series which converges to Pi. series :: Integral i => Series i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the Rabinowitz-Wagon -- series; -- http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf -- http://www.mathpropress.com/stan/bibliography/spigot.pdf.

module Factory.Math.Implementations.Pi.Spigot.RabinowitzWagon -- | Defines a series which converges to Pi. series :: Integral i => Series i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Implements a spigot-algorithm; -- http://en.wikipedia.org/wiki/Spigot_algorithm.
Uses the traditional algorithm, rather than the unbounded -- algorithm described by -- http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf.

module Factory.Math.Implementations.Pi.Spigot.Spigot -- | The constant base in which we want the resulting value of Pi to -- be expressed. decimal :: I -- |

Initialises a spigot-table with the row of -- coefficients.
Ensures that the row has suffient terms to accurately generate the -- required number of digits.
Extracts only those digits which are guaranteed to be -- accurate.
CAVEAT: the result is returned as an Integer, i.e. without -- any decimal point.

openI :: Series I -> DecimalDigits -> Integer -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the set of -- Spigot-algorithms which have been implemented.

module Factory.Math.Implementations.Pi.Spigot.Algorithm -- | Define those Spigot-algorithms which have been implemented. data Algorithm -- | A continued fraction discovered by Gosper. Gosper :: Algorithm -- | A continued fraction discovered by Rabinowitz and -- Wagon. RabinowitzWagon :: Algorithm instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Determines the Arithmetic-geometric -- mean; -- http://en.wikipedia.org/wiki/Arithmetic-geometric_mean.

module Factory.Math.ArithmeticGeometricMean -- | The type of the arithmetic mean; -- http://en.wikipedia.org/wiki/Arithmetic_mean. type ArithmeticMean = Rational -- | The type of the geometric mean; -- http://en.wikipedia.org/wiki/Geometric_mean. type GeometricMean = Rational -- | Encapsulates both arithmetic and geometric means. type AGM = (ArithmeticMean, GeometricMean) -- | Returns an infinite list which converges on the -- Arithmetic-geometric mean. convergeToAGM :: Algorithmic squareRootAlgorithm => squareRootAlgorithm -> DecimalDigits -> AGM -> [AGM] -- | Returns the bounds within which the AGM has been constrained. spread :: AGM -> Rational -- | Accessor. getArithmeticMean :: AGM -> ArithmeticMean -- | Accessor. getGeometricMean :: AGM -> GeometricMean -- | Checks that both means are positive, as required for the -- geometric mean to be consistently real. isValid :: AGM -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Implements the Brent-Salamin (AKA Gauss-Legendre) -- algorithm; -- http://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm, -- http://mathworld.wolfram.com/Brent-SalaminFormula.html, -- http://www.pi314.net/eng/salamin.php.
The precision of the result approximately doubles for each -- iteration.

-- --

CAVEAT Assumptions on the convergence-rate result -- in rounding-errors, when only a small number of digits are -- requested.

module Factory.Math.Implementations.Pi.AGM.BrentSalamin -- |

Returns Pi, accurate to the specified number of decimal -- digits.
This algorithm is based on the arithmetic-geometric mean of -- 1 and (1 / sqrt 2), but there are many confusingly -- similar formulations. The algorithm I've used here, where a -- is the arithmetic mean and g is the geometric -- mean, is equivalent to other common formulations:

-- --

--   pi = (a[N-1] + g[N-1])^2 / (1 - sum [2^n * (a[n] - g[n])^2])			where n = [0 .. N-1]
--   => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 - 2*a[n]*g[n] + g[n]^2)])
--   => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 + 2*a[n]*g[n] + g[n]^2 - 4*a[n]*g[n])])
--   => 4*a[N]^2 / (1 - sum [2^n * ((a[n] + g[n])^2 - 4*a[n]*g[n])])
--   => 4*a[N]^2 / (1 - sum [2^(n-1) * 4 * (a[n-1]^2 - g[n-1]^2)])			where n = [1 .. N]
--   => 4*a[N]^2 / (1 - sum [2^(n+1) * (a[n-1]^2 - g[n-1]^2)])
--

openR :: Algorithmic squareRootAlgorithm => squareRootAlgorithm -> DecimalDigits -> Rational -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the set of -- Arithmetic-geometric Mean-type Pi-algorithms which have -- been implemented; currently just one.

module Factory.Math.Implementations.Pi.AGM.Algorithm -- | Defines the available algorithms. data Algorithm squareRootAlgorithm BrentSalamin :: squareRootAlgorithm -> Algorithm squareRootAlgorithm instance Eq squareRootAlgorithm => Eq (Algorithm squareRootAlgorithm) instance Read squareRootAlgorithm => Read (Algorithm squareRootAlgorithm) instance Show squareRootAlgorithm => Show (Algorithm squareRootAlgorithm) instance Algorithmic squareRootAlgorithm => Algorithmic (Algorithm squareRootAlgorithm) instance Defaultable squareRootAlgorithm => Defaultable (Algorithm squareRootAlgorithm) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines a prime-wheel, for use -- in prime-number generation; -- http://en.wikipedia.org/wiki/Wheel_factorization.

module Factory.Data.PrimeWheel -- | Couples a candidate prime with a rolling wheel, to define the -- distance rolled. type Distance i = (i, [i]) -- | The size of the wheel, measured by the number of primes from -- which it is composed. type NPrimes = Int -- | An infinite increasing sequence, of the multiples of a specific prime. type PrimeMultiples i = [i] -- |

A conceptual wheel, with irregularly spaced spokes; -- http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Prime_Wheels.
On being rolled, the trace of the spokes, identifies candidates -- which are coprime to those primes from which the wheel -- was composed.
One can alternatively view this as a set of vertical nested rings, -- each with a prime circumference, and touching at its lowest -- point. Each has a single mark on its circumference, which when -- rolled identifies multiples of that circumference. When the -- complete set is rolled, from the state where all marks are coincident, -- all multiples of the set of primes, are traced.
CAVEAT: The distance required to return to this state (the wheel's -- circumference), grows rapidly with the number of primes:

-- --

--   zip [0 ..] . scanl (*) 1 $ [2,3,5,7,11,13,17,19,23,29,31]
--   [(0,1),(1,2),(2,6),(3,30),(4,210),(5,2310),(6,30030),(7,510510),(8,9699690),(9,223092870),(10,6469693230),(11,200560490130)]
--

-- --

The number of spokes also grows rapidly with the number of -- primes:

-- --

--   zip [0 ..] . scanl (*) 1 . map pred $ [2,3,5,7,11,13,17,19,23,29,31]
--   [(0,1),(1,1),(2,2),(3,8),(4,48),(5,480),(6,5760),(7,92160),(8,1658880),(9,36495360),(10,1021870080),(11,30656102400)]
--

data PrimeWheel i -- |

The optimal number of low primes from which to build the -- wheel, grows with the number of primes required; the -- circumference should be approximately the square-root of -- the number of integers it will be required to sieve.
CAVEAT: one greater than this is returned, which empirically seems -- better.

estimateOptimalSize :: Integral i => i -> NPrimes -- |

Generates multiples of the specified prime, starting from its -- square, skipping those multiples of the low primes from which -- the specified PrimeWheel was composed, and which therefore, the -- wheel won't generate as candidates. Eg:

-- --

--   Prime	Rotating PrimeWheel 3	Output
--   =====	=====================	======
--   7	[4,2,4,2,4,6,2,6]	[49,77,91,119,133,161,203,217,259 ..]
--   11	[2,4,2,4,6,2,6,4]	[121,143,187,209,253,319,341,407 ..]
--   13	[4,2,4,6,2,6,4,2]	[169,221,247,299,377,403,481,533,559 ..]
--

generateMultiples :: Integral i => i -> [i] -> [i] -- | Generate an infinite, increasing sequence of candidate primes, from -- the specified wheel. roll :: Integral i => PrimeWheel i -> [Distance i] -- | Generates a new candidate prime, from a rolling wheel, and the -- current candidate. rotate :: Integral i => Distance i -> Distance i -- | Smart constructor for a wheel from the specified number of low -- primes. -- --

The optimal number of low primes from which to build the -- wheel, grows with the number of primes required; the -- circumference should be approximately the square-root of -- the number of integers it will be required to sieve.
The sequence of gaps between spokes on the wheel is -- symmetrical under reflection; though two values lie on -- the axis, that aren't part of this symmetry. Eg:

-- --

--   nPrimes	Gaps
--   ======	====
--   0	[1]
--   1	[2]	--The terminal gap for all subsequent wheels is '2'; [(succ circumference `mod` circumference) - (pred circumference `mod` circumference)].
--   2	[4,2]	--Both points are on the axis, so the symmetry isn't yet clear.
--   3	[6,4,2,4,2,4,6,2]
--   4	[10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2]
--

-- -- Exploitation of this property has proved counter-productive, probably -- because it requires strict evaluation, exposing the user to the -- full cost of inadvertently choosing a wheel, which in practice, -- is rotated less than once. mkPrimeWheel :: Integral i => NPrimes -> PrimeWheel i -- | The circumference of the specified PrimeWheel. getCircumference :: Integral i => PrimeWheel i -> i -- | The number of spokes in the specified PrimeWheel. getSpokeCount :: Integral i => PrimeWheel i -> i instance Show i => Show (PrimeWheel i) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Generates the constant bounded list of -- prime-numbers, using the Sieve of Atkin; -- http://en.wikipedia.org/wiki/Sieve_of_Atkin.
cr.yp.to/papers/primesieves-19990826.pdf.
The implementation; has been optimised using a wheel of -- static, but parameterised, size; has been parallelized; is -- polymorphic, but with a specialisation for type Int.

-- --

CAVEAT The Int-specialisation is -- implemented by a rewrite-rule, which is very -- fragile.

module Factory.Math.Implementations.Primes.SieveOfAtkin -- |

Generates the constant bounded list of -- prime-numbers.
http://cr.yp.to/papers/primesieves-19990826.pdf

sieveOfAtkin :: (NFData i, Ix i, Integral i) => NPrimes -> i -> [i] instance Eq PolynomialType -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Generates the constant, conceptually infinite, list of -- prime-numbers, using the Sieve of Eratosthenes; -- http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
Based on -- http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.
The implementation; has been optimised using a wheel of -- static, but parameterised, size; is polymorphic, but with a -- specialisation for type Int.

-- --

CAVEAT The Int-specialisation is -- implemented by a rewrite-rule, which is very -- fragile.

module Factory.Math.Implementations.Primes.SieveOfEratosthenes -- |

A refinement of the Sieve Of Eratosthenes, which pre-sieves -- candidates, selecting only those coprime to the specified short -- sequence of low prime-numbers.
The short sequence of initial primes are represented by a -- PrimeWheel, of parameterised, but static, size; -- http://en.wikipedia.org/wiki/Wheel_factorization.
The algorithm requires one to record multiples of previously -- discovered primes, allowing composite candidates to be -- eliminated by comparison.
Because each list of multiples, starts with the -- square of the prime from which it was generated, the vast -- majority will be larger than the maximum prime ultimately demanded, -- and the effort of constructing and storing this list, is consequently -- wasted. Many implementations solve this, by requiring specification of -- the maximum prime required, thus allowing the construction of -- redundant lists of multiples to be avoided.
This implementation doesn't impose that constraint, leaving a -- requirement for rapid storage, which is supported by -- appending the list of prime-multiples, to a -- queue. If a large enough candidate is ever generated, to match -- the head of the list of prime-multiples, at the -- head of this queue, then the whole list of -- prime-multiples is dropped from the queue, but the tail -- of this list of prime-multiples, for which there is now a high -- likelyhood of a subsequent match, must now be re-recorded. A -- queue doesn't support efficient random insertion, so a -- Map is used for these subsequent multiples. This solution is -- faster than just using a Data.PQueue.Min.
CAVEAT: has linear O(n) space-complexity.

sieveOfEratosthenes :: Integral i => NPrimes -> [i] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Provides a polymorphic algorithm, to unfold a list into a -- tree, to which an associative binary operator is then applied -- to re-fold the tree to a scalar.
Implementations of this strategy have been provided for -- addition and multiplication, though other associative -- binary operators, like gcd or lcm could also be -- used.
Where the contents of the list are consecutive, a more efficient -- implementation is available in Factory.Data.Interval.

module Factory.Math.DivideAndConquer -- |

The ratio of the original list-length at which to bisect.
CAVEAT: the value can overflow.

type BisectionRatio = Ratio Int -- | The list-length beneath which to terminate bisection. type MinLength = Int -- |

Reduces a list to a single scalar encapsulated in a Monoid, -- using a divide-and-conquer strategy, bisecting the list and -- recursively evaluating each part; -- http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.
By choosing a bisectionRatio other than (1 % 2), -- the bisection can be made asymmetrical. The specified ratio represents -- the length of the left-hand portion, over the original list-length; -- eg. (1 % 3) results in the first part, half the length of the -- second.
This process of recursive bisection, is terminated beneath the -- specified minimum list-length, after which the monoid's binary -- operator is directly folded over the list.
One can view this as a -- http://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29, -- in which the list is exploded into a binary tree-structure (each leaf -- of which contains a list of up to minLength integers, and -- each node of which contains an associative binary operator), and then -- collapsed to a scalar, by application of the operators.

divideAndConquer :: Monoid monoid => BisectionRatio -> MinLength -> [monoid] -> monoid -- |

Multiplies the specified list of numbers.
Since the result can be large, divideAndConquer is used in -- an attempt to form operands of a similar order of magnitude, which -- creates scope for the use of more efficient -- multiplication-algorithms.

product' :: Num n => BisectionRatio -> MinLength -> [n] -> n -- |

Sums the specified list of numbers.
Since the result can be large, divideAndConquer is used in -- an attempt to form operands of a similar order of magnitude, which -- creates scope for the use of more efficient multiplication-algorithms. -- Multiplication is required for the addition of -- Rational numbers by cross-multiplication; this function is -- unlikely to be useful for other numbers.

sum' :: Num n => BisectionRatio -> MinLength -> [n] -> n -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a ring and operations on its members.
http://en.wikipedia.org/wiki/Ring_%28mathematics%29.
http://www.numericana.com/answer/rings.htm.

module Factory.Data.Ring -- |

Define both the operations applicable to all members of the -- ring, and its mandatory members.
Minimal definition; =+=, =*=, -- additiveInverse, multiplicativeIdentity, -- additiveIdentity.

class Ring r where l =-= r = l =+= additiveInverse r square r = r =*= r (=+=) :: Ring r => r -> r -> r (=*=) :: Ring r => r -> r -> r additiveInverse :: Ring r => r -> r multiplicativeIdentity :: Ring r => r additiveIdentity :: Ring r => r (=-=) :: Ring r => r -> r -> r square :: Ring r => r -> r -- | Returns the product of the list of ring-members. product' :: Ring r => BisectionRatio -> MinLength -> [r] -> r -- | Returns the sum of the list of ring-members. sum' :: Ring r => BisectionRatio -> MinLength -> [r] -> r -- |

Raise a ring-member to the specified positive integral -- power.
Exponentiation is implemented as a sequence of either squares of, -- or multiplications by, the ring-member; -- http://en.wikipedia.org/wiki/Exponentiation_by_squaring.

(=^) :: (Eq r, Integral power, Ring r, Show power) => r -> power -> r instance Read p => Read (Product p) instance Show p => Show (Product p) instance Read s => Read (Sum s) instance Show s => Show (Sum s) instance Ring r => Monoid (Sum r) instance Ring r => Monoid (Product r) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a Quotient Ring; -- http://en.wikipedia.org/wiki/Quotient_ring.
This is a ring composed from a residue-class resulting from -- modular division.

module Factory.Data.QuotientRing -- | Defines a sub-class of Ring, in which division is implemented. class Ring q => QuotientRing q quotRem' :: QuotientRing q => q -> q -> (q, q) -- | Returns the quotient, after division of the two specified -- QuotientRings. quot' :: QuotientRing q => q -> q -> q -- | Returns the remainder, after division of the two specified -- QuotientRings. rem' :: QuotientRing q => q -> q -> q -- |

True if the two specified QuotientRings are -- congruent in modulo-arithmetic, where the modulus -- is a third QuotientRing.
http://www.usna.edu/Users/math/wdj/book/node74.html.

areCongruentModulo :: (Eq q, QuotientRing q) => q -> q -> q -> Bool -- | True if the second operand divides the first. isDivisibleBy :: (Eq q, QuotientRing q) => q -> q -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a http://en.wikipedia.org/wiki/Monomial and -- operations on it.
A monomial is merely a polynomial with a single -- non-zero term; cf. Binomial.

module Factory.Data.Monomial -- |

The type of an arbitrary monomial.
CAVEAT: though a monomial has an integral power, this -- contraint is only imposed at the function-level.

type Monomial coefficient exponent = (coefficient, exponent) -- | Double the specified Monomial. double :: Num c => Monomial c e -> Monomial c e -- | Reduce the coefficient using modular arithmetic. mod' :: Integral c => Monomial c e -> c -> Monomial c e -- | Negate the coefficient. negateCoefficient :: Num c => Monomial c e -> Monomial c e -- | Convert the type of the coefficient. realCoefficientToFrac :: (Real r, Fractional f) => Monomial r e -> Monomial f e -- | Shift the coefficient, by the specified amount. shiftCoefficient :: Num c => Monomial c e -> c -> Monomial c e -- | Shift the exponent, by the specified amount. shiftExponent :: Num e => Monomial c e -> e -> Monomial c e -- | Square the specified Monomial. square :: (Num c, Num e) => Monomial c e -> Monomial c e -- | Accessor. getExponent :: Monomial c e -> e -- | Accessor. getCoefficient :: Monomial c e -> c -- | Compares the exponents of the specified Monomials. (<=>) :: Ord e => Monomial c e -> Monomial c e -> Ordering -- | Divide the two specified Monomials. () :: (Eq c, Fractional c, Num e) => Monomial c e -> Monomial c e -> Monomial c e -- | Multiply the two specified Monomials. (<*>) :: (Num c, Num e) => Monomial c e -> Monomial c e -> Monomial c e -- | True if the exponents are equal. (=~) :: Eq e => Monomial c e -> Monomial c e -> Bool -- |

True if the exponent is both integral and -- non-negative.
CAVEAT: one can't even call this function unless the -- exponent is integral.

isMonomial :: Integral e => Monomial c e -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a http://en.wikipedia.org/wiki/Univariate -- polynomial and operations on it.
http://en.wikipedia.org/wiki/Polynomial.
http://mathworld.wolfram.com/Polynomial.html.

module Factory.Data.Polynomial -- |

The type of an arbitrary univariate polynomial; actually -- it's more general, since it permits negative powers -- (http://en.wikipedia.org/wiki/Laurent_polynomials). It can't -- describe multivariate polynomials, which would require a list -- of exponents. Rather than requiring the exponent to -- implement the type-class Integral, this is implemented -- at the function-level, as required.
The structure permits gaps between exponents, in which -- coefficients are inferred to be zero, thus enabling efficient -- representation of sparse polynomials.
CAVEAT: the MonomialList is required to; be ordered by -- descending exponent (ie. reverse -- http://en.wikipedia.org/wiki/Monomial_order); have had zero -- coefficients removed; and to have had like terms merged; so the -- raw data-constructor isn't exported.

data Polynomial coefficient exponent -- | Constructs a polynomial with zero terms. zero :: Polynomial c e -- | Constructs a constant monomial, independent of the -- indeterminate. one :: (Eq c, Num c, Num e) => Polynomial c e -- |

Evaluate the polynomial at a specific -- indeterminate.
CAVEAT: requires positive exponents; but it wouldn't really be a -- polynomial otherwise.
If the polynomial is very sparse, this may be inefficient, -- since it memoizes the complete sequence of powers up to the -- polynomial's degree.

evaluate :: (Num n, Integral e, Show e) => n -> Polynomial n e -> n -- |

Return the degree (AKA order) of the -- polynomial.
http://en.wikipedia.org/wiki/Degree_of_a_polynomial.
http://mathworld.wolfram.com/PolynomialDegree.html.

getDegree :: Num e => Polynomial c e -> e -- | Return the highest-degree monomial. getLeadingTerm :: Polynomial c e -> Monomial c e -- |

Transforms the data behind the constructor.
CAVEAT: similar to fmap, but Polynomial isn't an -- instance of Functor since we may want to operate on both -- type-parameters.
CAVEAT: the caller is required to re-normalise the -- resulting polynomial depending on the nature of the transformation of -- the data.

lift :: (MonomialList c1 e1 -> MonomialList c2 e2) -> Polynomial c1 e1 -> Polynomial c2 e2 -- | Reduces all the coefficients using modular arithmetic. mod' :: Integral c => Polynomial c e -> c -> Polynomial c e -- | Sorts into descending order of exponents, groups like -- exponents, and calls pruneCoefficients. normalise :: (Eq c, Num c, Ord e) => Polynomial c e -> Polynomial c e -- |

Raise a polynomial to the specified positive integral -- power, but using modulo-arithmetic.
Whilst one could naively implement this as (x Data.Ring.=^ n) -- mod m, this will result in arithmetic operatons on -- unnecessarily big integers.

raiseModulo :: (Integral c, Integral power, Num e, Ord e, Show power) => Polynomial c e -> power -> c -> Polynomial c e -- | Convert the type of the coefficients. realCoefficientsToFrac :: (Real r, Fractional f) => Polynomial r e -> Polynomial f e -- | Returns the number of non-zero terms in the polynomial. terms :: Polynomial c e -> Int -- | Constructs an arbitrary zeroeth-degree polynomial, ie. -- independent of the indeterminate. mkConstant :: (Eq c, Num c, Num e) => c -> Polynomial c e -- | Constructs an arbitrary first-degree polynomial. mkLinear :: (Eq c, Num c, Num e) => c -> c -> Polynomial c e -- | Smart constructor. Constructs an arbitrary polynomial. mkPolynomial :: (Eq c, Num c, Ord e) => MonomialList c e -> Polynomial c e -- |

Scale-up the specified polynomial by a constant -- monomial factor.
http://en.wikipedia.org/wiki/Scalar_multiplication.

(*=) :: (Eq c, Num c, Num e) => Polynomial c e -> Monomial c e -> Polynomial c e -- |

True if the two specified polynomials are -- congruent in modulo-arithmetic.
http://planetmath.org/encyclopedia/PolynomialCongruence.html.

areCongruentModulo :: (Integral c, Num e, Ord e) => Polynomial c e -> Polynomial c e -> c -> Bool -- | True if the exponents of successive terms are in -- ascending order. inAscendingOrder :: Ord e => Polynomial c e -> Bool -- | True if the exponents of successive terms are in -- descending order. inDescendingOrder :: Ord e => Polynomial c e -> Bool -- |

True if the leading coefficient is one.
http://en.wikipedia.org/wiki/Monic_polynomial#Classifications.

isMonic :: (Eq c, Num c) => Polynomial c e -> Bool -- | True if there's exactly one term. isMonomial :: Polynomial c e -> Bool -- | True if no term has a coefficient of zero and the -- exponents of successive terms are in descending order. isNormalised :: (Eq c, Num c, Ord e) => Polynomial c e -> Bool -- | True if all exponents are positive integers as required. isPolynomial :: Integral e => Polynomial c e -> Bool -- | True if there are zero terms. isZero :: Polynomial c e -> Bool instance (Eq coefficient, Eq exponent) => Eq (Polynomial coefficient exponent) instance (Show coefficient, Show exponent) => Show (Polynomial coefficient exponent) instance (Eq c, Fractional c, Num e, Ord e) => QuotientRing (Polynomial c e) instance (Eq c, Num c, Num e, Ord e) => Ring (Polynomial c e) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a monic polynomial; -- <http:en.wikipedia.orgwiki/Monic_polynomial#Classifications>; -- ie. in which the coefficient of the leading term is -- one.

module Factory.Data.MonicPolynomial -- | A type of Polynomial, in which the leading term is -- required to have a coefficient of one. data MonicPolynomial c e -- | Smart constructor. Constructs an arbitrary monic polynomial. mkMonicPolynomial :: (Eq c, Num c, Ord e, Show c, Show e) => Polynomial c e -> MonicPolynomial c e instance (Eq c, Eq e) => Eq (MonicPolynomial c e) instance (Show c, Show e) => Show (MonicPolynomial c e) instance (Eq c, Num c, Num e, Ord e, Show c, Show e) => QuotientRing (MonicPolynomial c e) instance (Eq c, Num c, Num e, Ord e, Show c, Show e) => Ring (MonicPolynomial c e) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a bounded set of, typically integral, quantities.
Operations have been defined, on the list of consecutive -- quantities delimited by these endpoints.
The point is that if the list is composed from consecutive -- quantities, the intermediate values can be inferred, rather than -- physically represented.

-- --

CAVEATS

-- --

The API was driven top-down by its caller's requirements, rather -- than a bottom-up attempt to provide a complete interface. consequently -- there may be omissions from the view point of future callers.
Thought similar to the mathematical concept of an interval, -- the latter technically relates to real numbers; -- http://en.wikipedia.org/wiki/Interval_%28mathematics%29.
No account has been made for semi-closed or open -- intervals.

module Factory.Data.Interval -- | Defines a closed (inclusive) interval of consecutive values. type Interval endPoint = (endPoint, endPoint) -- | Construct the unsigned closed unit-interval; -- http://en.wikipedia.org/wiki/Unit_interval. closedUnitInterval :: Num n => Interval n -- | Construct an interval from a bounded type. mkBounded :: Bounded endPoint => Interval endPoint -- | True if the specified value is within the inclusive bounds of the -- interval. elem' :: Ord endPoint => endPoint -> Interval endPoint -> Bool -- | Swap the end-points where they were originally reversed, but -- otherwise do nothing. normalise :: Ord endPoint => Interval endPoint -> Interval endPoint -- |

Multiplies the consecutive sequence of integers within -- Interval.
Since the result can be large, divideAndConquer is used to -- form operands of a similar order of magnitude, thus improving the -- efficiency of the big-number multiplication.

product' :: (Integral i, Show i) => Ratio i -> i -> Interval i -> i -- | Shift of both end-points of the interval by the -- specified amount. shift :: Num endPoint => endPoint -> Interval endPoint -> Interval endPoint -- | Bisect the interval at the specified end-point; which -- should be between the two existing end-points. splitAt' :: (Enum endPoint, Num endPoint, Ord endPoint, Show endPoint) => endPoint -> Interval endPoint -> (Interval endPoint, Interval endPoint) -- |

Converts Interval to a list by enumerating the values.
CAVEAT: produces rather odd results for Fractional types, -- but no stranger than considering such types Enumerable.

toList :: Enum endPoint => Interval endPoint -> [endPoint] -- | Accessor. getMinBound :: Interval endPoint -> endPoint -- | Accessor. getMaxBound :: Interval endPoint -> endPoint -- | Construct an interval from a single value. precisely :: endPoint -> Interval endPoint -- | True if getMinBound exceeds getMaxBound extent. isReversed :: Ord endPoint => Interval endPoint -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Miscellaneous functions for -- probability-distributions.

module Factory.Math.Probability -- | Describes a continuous probability-distribution; -- http://en.wikipedia.org/wiki/List_of_probability_distributions#Continuous_distributions. data ContinuousDistribution f -- | Defines a Uniform-distribution within a closed interval; -- http://en.wikipedia.org/wiki/Uniform_distribution. UniformDistribution :: (Interval f) -> ContinuousDistribution f -- | Defines a Normal-distribution with a particular mean and -- variance; -- http://en.wikipedia.org/wiki/Normal_distribution. NormalDistribution :: f -> f -> ContinuousDistribution f -- | Describes a discrete probability-distribution; -- http://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions. data DiscreteDistribution f PoissonDistribution :: f -> DiscreteDistribution f -- |

Converts a pair of independent uniformly distributed random -- numbers, within the semi-closed unit interval (0,1], to -- a pair of independent normally distributed random numbers, of -- standardized mean=0, and variance=1.
http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform.

boxMullerTransform :: (Floating f, Ord f, Show f) => (f, f) -> (f, f) -- |

Uses the supplied random-number generator, to generate a -- conceptually infinite list, of normally distributed random -- numbers, with standardized mean=0, and variance=1.
http://en.wikipedia.org/wiki/Normal_distribution, -- http://mathworld.wolfram.com/NormalDistribution.html.

generateStandardizedNormalDistribution :: (RealFloat f, Show f, Random f, RandomGen randomGen) => randomGen -> [f] -- |

Generates a random sample-population, with the specified -- continuous probability-distribution.
When a Normal distribution is requested, the generated -- population will only tend towards the requested mean and -- variance of, as the sample-size tends towards infinity. Whilst -- one could arrange for these criteria to be precisely met for any -- sample-size, the sample would lose a degree of randomness as a -- result.

generateContinuousPopulation :: (RealFloat f, Show f, Random f, RandomGen randomGen) => Int -> ContinuousDistribution f -> randomGen -> [f] -- |

Uses the supplied random-number generator, to generate a -- conceptually infinite list, of random integers conforming to the -- Poisson distribution (mean=lambda, -- variance=lambda).
http://en.wikipedia.org/wiki/Poisson_distribution.
CAVEAT: uses an algorithm by Knuth, which having a linear -- time-complexity in lambda, can be intolerably slow; also, -- the term exp $ negate lambda, underflows for large -- lambda; so for large lambda, this implementation returns -- the appropriate NormalDistribution, which is similar for large -- lambda.

generatePoissonDistribution :: (Integral events, RealFloat lambda, Show lambda, Random lambda, RandomGen randomGen) => lambda -> randomGen -> [events] -- | Generates a random sample-population, with the specified discrete -- probability-distribution. generateDiscretePopulation :: (Ord f, RealFloat f, Show f, Random f, RandomGen randomGen, Integral events) => Int -> DiscreteDistribution f -> randomGen -> [events] instance Eq f => Eq (ContinuousDistribution f) instance Read f => Read (ContinuousDistribution f) instance Show f => Show (ContinuousDistribution f) instance Eq f => Eq (DiscreteDistribution f) instance Read f => Read (DiscreteDistribution f) instance Show f => Show (DiscreteDistribution f) instance (Num f, Ord f, Show f) => SelfValidator (DiscreteDistribution f) instance (Num a, Ord a, Show a) => SelfValidator (ContinuousDistribution a) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a simple numeric type, designed to contain an -- exponential number.
http://en.wikipedia.org/wiki/Exponentiation.

module Factory.Data.Exponential -- | Describes an exponential, in terms of its base and -- exponent. type Exponential base exponent = (base, exponent) -- | Evaluate the specified Exponential, returning the resulting -- number. evaluate :: (Num base, Integral exponent) => Exponential base exponent -> base -- | Invert the value, by negating the exponent. invert :: Num exponent => Exponential base exponent -> Exponential base exponent -- | Accessor. getBase :: Exponential base exponent -> base -- | Accessor. getExponent :: Exponential base exponent -> exponent -- |

Construct an Exponential merely raised to the 1st -- power.
The value of the resulting exponential is the same as specified -- base; -- http://en.wikipedia.org/wiki/Identity_element.

rightIdentity :: Num exponent => base -> Exponential base exponent -- | Raise the specified Exponential to a power. (<^) :: Num exponent => Exponential base exponent -> exponent -> Exponential base exponent -- | True if the bases are equal. (=~) :: Eq base => Exponential base exponent -> Exponential base exponent -> Bool -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a list of prime factors.
The product of this list of prime-factors represents the -- composite integer from which they were originally -- extracted.

module Factory.Data.PrimeFactors -- |

Each element of this list represents one prime-factor, -- expressed as an exponential with a prime base, of the -- original integer.
Whilst it only makes sense for both the base and -- exponent to be integral, these constrains are applied at the -- function-level as required.

type Factors base exponent = [Exponential base exponent] -- |

Insert a Exponential, into a list representing a product of -- prime factors, multiplying with any incumbent of like -- base.
The list should be sorted by increasing base.
Preserves the sort-order.
CAVEAT: this is tolerably efficient for sporadic insertion; to -- insert a list, use >*<.

insert' :: (Ord base, Num exponent) => Exponential base exponent -> Factors base exponent -> Factors base exponent -- | Multiply a list of prime factors. product' :: (Num base, Integral exponent) => BisectionRatio -> MinLength -> Factors base exponent -> base -- |

Sorts a list representing a product of prime factors by -- increasing base.
Multiplies Exponentials of similar base.

reduce :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent -- |

Multiplies two lists each representing a product of prime -- factors, and sorted by increasing base.
Preserves the sort-order.

(>*<) :: (Ord base, Num exponent, Ord exponent) => Factors base exponent -> Factors base exponent -> Factors base exponent -- |

Divides two lists, each representing a product of prime -- factors, and sorted by increasing base.
Preserves the sort-order.

(>/<) :: (Integral base, Integral exponent) => Factors base exponent -> Factors base exponent -> (Factors base exponent, Factors base exponent) -- |

Raise the product of a list prime factors to the specified -- power.
CAVEAT: this merely involves raising each element to the specified -- power; cf. raising a polynomial to a power.

(>^) :: Num exponent => Factors base exponent -> exponent -> Factors base exponent -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Provides implementations of the class Algorithmic.
Provides additional functions related to factorials, but -- which depends on a specific implementation, and which therefore can't -- be accessed throught the class-interface.
http://en.wikipedia.org/wiki/Factorial.
http://mathworld.wolfram.com/Factorial.html.
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm.

module Factory.Math.Implementations.Factorial -- | The algorithms by which factorial has been implemented. data Algorithm -- | The integers from which the factorial is composed, are -- multiplied using Data.Interval.product'. Bisection :: Algorithm -- | The prime factors of the factorial are extracted, then -- raised to the appropriate power, before multiplication. PrimeFactorisation :: Algorithm -- |

Returns the prime factors, of the factorial of the -- specifed integer.
Precisely all the primes less than or equal to the specified -- integer n, are included in n!; only the multiplicity of -- each of these known prime components need be determined.
http://en.wikipedia.org/wiki/Factorial#Number_theory.
CAVEAT: currently a hotspot.

primeFactors :: Integral base => base -> Factors base base -- | Returns the rising factorial; -- http://mathworld.wolfram.com/RisingFactorial.html risingFactorial :: (Integral i, Show i) => i -> i -> i -- | Returns the falling factorial; -- http://mathworld.wolfram.com/FallingFactorial.html fallingFactorial :: (Integral i, Show i) => i -> i -> i -- |

Returns the ratio of two factorials.
It is more efficient than evaluating both factorials, and then -- dividing.
For more complex combinations of factorials, such as in the -- Binomial coefficient, extract the prime factors using -- primeFactors then manipulate them using the module -- Data.PrimeFactors, and evaluate it using by -- Data.PrimeFactors.product'.

(!/!) :: (Integral i, Fractional f, Show i) => i -> i -> f instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the Borwein series for -- Pi; -- http://en.wikipedia.org/wiki/Borwein%27s_algorithm#Jonathan_Borwein_and_Peter_Borwein.27s_Version_.281993.29

module Factory.Math.Implementations.Pi.Borwein.Borwein1993 -- | Defines the parameters of the Borwein series. series :: (Algorithmic squareRootAlgorithm, Algorithmic factorialAlgorithm) => Series squareRootAlgorithm factorialAlgorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the set of Borwein-type -- algorithms (currently only one) which have been implemented; -- http://www.pi314.net/eng/borwein.php.

module Factory.Math.Implementations.Pi.Borwein.Algorithm -- |

Define those Borwein-series which have been -- implemented.
Though currently there's only one, provision has been made for the -- addition of more.

data Algorithm squareRootAlgorithm factorialAlgorithm -- | http://en.wikipedia.org/wiki/Borwein%27s_algorithm. Borwein1993 :: squareRootAlgorithm -> factorialAlgorithm -> Algorithm squareRootAlgorithm factorialAlgorithm instance (Eq squareRootAlgorithm, Eq factorialAlgorithm) => Eq (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Read squareRootAlgorithm, Read factorialAlgorithm) => Read (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Show squareRootAlgorithm, Show factorialAlgorithm) => Show (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Algorithmic squareRootAlgorithm, Algorithmic factorialAlgorithm) => Algorithmic (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Defaultable squareRootAlgorithm, Defaultable factorialAlgorithm) => Defaultable (Algorithm squareRootAlgorithm factorialAlgorithm) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the Chudnovsky series -- for Pi; http://en.wikipedia.org/wiki/Pi.

module Factory.Math.Implementations.Pi.Ramanujan.Chudnovsky -- | Defines the parameters of the Chudnovsky series. series :: (Algorithmic squareRootAlgorithm, Algorithmic factorialAlgorithm) => Series squareRootAlgorithm factorialAlgorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the Ramanujan series -- for Pi; -- http://planetmath.org/encyclopedia/RamanujansFormulaForPi.html.

module Factory.Math.Implementations.Pi.Ramanujan.Classic -- | Defines the parameters of the Ramanujan series. series :: (Algorithmic squareRootAlgorithm, Algorithmic factorialAlgorithm) => Series squareRootAlgorithm factorialAlgorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Defines the set of -- Ramanujan-type algorithms which have been implemented; -- http://en.wikipedia.org/wiki/Pi.

module Factory.Math.Implementations.Pi.Ramanujan.Algorithm -- | Define those Ramanujan-series which have been implemented. data Algorithm squareRootAlgorithm factorialAlgorithm -- | The original version. Classic :: squareRootAlgorithm -> factorialAlgorithm -> Algorithm squareRootAlgorithm factorialAlgorithm -- | A variant found by the Chudnovsky brothers. Chudnovsky :: squareRootAlgorithm -> factorialAlgorithm -> Algorithm squareRootAlgorithm factorialAlgorithm instance (Eq squareRootAlgorithm, Eq factorialAlgorithm) => Eq (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Read squareRootAlgorithm, Read factorialAlgorithm) => Read (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Show squareRootAlgorithm, Show factorialAlgorithm) => Show (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Algorithmic squareRootAlgorithm, Algorithmic factorialAlgorithm) => Algorithmic (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Defaultable squareRootAlgorithm, Defaultable factorialAlgorithm) => Defaultable (Algorithm squareRootAlgorithm factorialAlgorithm) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Miscellaneous statistics -- functions.

module Factory.Math.Statistics -- |

Determines the mean of the specified numbers; -- http://en.wikipedia.org/wiki/Mean.
Should the caller define the result-type as Rational, then -- it will be free from rounding-errors.

getMean :: (Foldable f, Real r, Fractional result) => f r -> result -- |

Determines the exact variance of the specified numbers; -- http://en.wikipedia.org/wiki/Variance.
Should the caller define the result-type as Rational, then -- it will be free from rounding-errors.

getVariance :: (Foldable f, Fractional variance, Functor f, Real r) => f r -> variance -- | Determines the standard-deviation of the specified numbers; -- http://en.wikipedia.org/wiki/Standard_deviation. getStandardDeviation :: (Foldable f, Floating result, Functor f, Real r) => f r -> result -- |

Determines the average absolute deviation of the specified -- numbers; -- http://en.wikipedia.org/wiki/Absolute_deviation#Average_absolute_deviation.
Should the caller define the result-type as Rational, then -- it will be free from rounding-errors.

getAverageAbsoluteDeviation :: (Foldable f, Fractional result, Functor f, Real r) => f r -> result -- | Determines the coefficient-of-variance of the specified -- numbers; http://en.wikipedia.org/wiki/Coefficient_of_variation. getCoefficientOfVariance :: (Foldable f, Eq result, Floating result, Functor f, Real r) => f r -> result -- | The number of unordered combinations of r objects taken -- from n; http://en.wikipedia.org/wiki/Combination. nCr :: (Algorithmic factorialAlgorithm, Integral i, Show i) => factorialAlgorithm -> i -> i -> i -- | The number of permutations of r objects taken from -- n; http://en.wikipedia.org/wiki/Permutations. nPr :: (Integral i, Show i) => i -> i -> i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Implements Algorithmic by a -- variety of methods.
CAVEAT

-- -- Caller may benefit from application of simplify before -- operating on the result; which though of the required accuracy, may -- not be the most concise rational number satisfying that criterion. module Factory.Math.Implementations.SquareRoot -- | The number of terms in a series. type Terms = Int -- | The algorithms by which the square-root has been implemented. data Algorithm -- | -- http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Bakhshali_approximation BakhshaliApproximation :: Algorithm -- | -- http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion. ContinuedFraction :: Algorithm -- | http://en.wikipedia.org/wiki/Halley%27s_method. HalleysMethod :: Algorithm -- | http://en.wikipedia.org/wiki/Newton%27s_method. NewtonRaphsonIteration :: Algorithm -- | -- http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Taylor_series. TaylorSeries :: Terms -> Algorithm instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Iterator Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm -- |

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.

module Factory.Math.PrimeFactorisation -- | Defines the methods expected of a factorisation-algorithm. class Algorithmic algorithm primeFactors :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> base -> Factors base Int -- |

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

maxBoundPrimeFactor :: Integral i => i -> i -- |

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.

smoothness :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] -- |

A constant, zero-indexed, conceptually infinite, list of the -- power-smoothness of all positive integers.
http://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers.

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

Filters smoothness, to derive the constant list of -- Hamming-numbers.
http://en.wikipedia.org/wiki/Regular_number.

regularNumbers :: (Algorithmic algorithm, NFData base, Integral base) => algorithm -> [base] -- |

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.

primePowerTotient :: (Integral base, Integral exponent) => Exponential base exponent -> base -- |

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.

eulersTotient :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> i -- |

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.

omega :: (Algorithmic algorithm, NFData i, Integral i) => algorithm -> [i] -- |

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.

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

AUTHOR Dr. Alistair Ward
DESCRIPTION Exports the Multiplicative -- Order of an integer, in a specific modular arithmetic.

module Factory.Math.MultiplicativeOrder -- |

The smallest positive integral power to which the specified -- integral base must be raised, to be congruent with one, in the -- specified modular arithmetic.
Based on -- http://rosettacode.org/wiki/Multiplicative_order#Haskell.
http://en.wikipedia.org/wiki/Multiplicative_order.
http://mathworld.wolfram.com/MultiplicativeOrder.html.

multiplicativeOrder :: (Algorithmic primeFactorisationAlgorithm, NFData i, Integral i, Show i) => primeFactorisationAlgorithm -> i -> i -> i -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Determines whether an integer is prime.
http://en.wikipedia.org/wiki/Primality_test.
http://primes.utm.edu/index.html
CAVEAT: it doesn't determine the prime-factors of composite -- numbers, just that they exist.

module Factory.Math.Implementations.Primality -- | The algorithms by which primality-testing has been implemented. data Algorithm factorisationAlgorithm -- | http://en.wikipedia.org/wiki/AKS_primality_test. AKS :: factorisationAlgorithm -> Algorithm factorisationAlgorithm -- | -- http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test. MillerRabin :: Algorithm factorisationAlgorithm instance Eq factorisationAlgorithm => Eq (Algorithm factorisationAlgorithm) instance Read factorisationAlgorithm => Read (Algorithm factorisationAlgorithm) instance Show factorisationAlgorithm => Show (Algorithm factorisationAlgorithm) instance Algorithmic factorisationAlgorithm => Algorithmic (Algorithm factorisationAlgorithm) instance Defaultable (Algorithm factorisationAlgorithm) -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Generates the constant, conceptually -- infinite, list of prime-numbers, using Trial -- Division.

module Factory.Math.Implementations.Primes.TrialDivision -- |

For each candidate, confirm indivisibility, by all primes -- smaller than its square-root.
The candidates to sieve, are generated by a PrimeWheel, of -- parameterised, but static, size; -- http://en.wikipedia.org/wiki/Wheel_factorization.

trialDivision :: Integral prime => NPrimes -> [prime] -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Generates the constant list of prime-numbers, by a variety -- of different algorithms.
http://www.haskell.org/haskellwiki/Prime_numbers.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.3936&rep=rep1&type=pdf.
http://larc.unt.edu/ian/pubs/sieve.pdf.

module Factory.Math.Implementations.Primes.Algorithm -- | The implemented methods by which the primes may be generated. data Algorithm -- | The Sieve of Atkin, optimised using a PrimeWheel of -- optimal size, for primes up to the specified maximum bound; -- http://en.wikipedia.org/wiki/Sieve_of_Atkin. SieveOfAtkin :: Integer -> Algorithm -- | The Sieve of Eratosthenes -- (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), optimised -- using a PrimeWheel. SieveOfEratosthenes :: NPrimes -> Algorithm -- | For each candidate, confirm indivisibility, by all primes -- smaller than its square-root, optimised using a -- PrimeWheel. TrialDivision :: NPrimes -> Algorithm -- | For each prime, the infinite list of candidates greater than -- its square, is filtered for indivisibility; -- http://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division. TurnersSieve :: Algorithm -- | wheelSieve. WheelSieve :: Int -> Algorithm instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Implements several different prime-factorisation algorithms.
http://www.tug.org/texinfohtml/coreutils.html#factor-invocation.

module Factory.Math.Implementations.PrimeFactorisation -- | The algorithms by which prime-factorisation has been implemented. data Algorithm -- | http://en.wikipedia.org/wiki/Fermat%27s_factorization_method. FermatsMethod :: Algorithm -- | http://en.wikipedia.org/wiki/Trial_division. TrialDivision :: Algorithm instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithmic Algorithm instance Defaultable Algorithm