-- 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, primality-testing, prime-factorisation ... @package factory @version 0.0.0.2 -- |

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 :: (Integral base, Integral decimal) => base -> decimal -> decimal -- | http://en.wikipedia.org/wiki/Digital_root. digitalRoot :: Integral 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) => 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 :: (Integral base, Integral decimal) => base -> decimal -> String -- |

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 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 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 -- 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 Algorithm algorithm factorial :: (Algorithm algorithm, Integral 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 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 Algorithm algorithm openR :: Algorithm algorithm => algorithm -> DecimalDigits -> Rational openI :: Algorithm algorithm => algorithm -> DecimalDigits -> Integer openS :: Algorithm 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 (Algorithm agm, Algorithm bbp, Algorithm borwein, Algorithm ramanujan, Algorithm spigot) => Algorithm (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 Algorithm 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 Algorithm Algorithm instance Defaultable Algorithm -- |

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

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 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 :: Num n => n -> [(n, n)] -- |

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.
(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 -- | 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) => i -> power -> i -> 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.

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

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 Algorithm algorithm squareRootFrom :: (Algorithm algorithm, Real operand) => algorithm -> Estimate -> DecimalDigits -> operand -> Result squareRoot :: (Algorithm algorithm, Real 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 => operand -> Estimate -- | True if the specified estimate for the square-root, is -- precise. isPrecise :: Real operand => operand -> Result -> Bool -- |

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 :: Algorithm 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

-- --

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

module Factory.Math.Primality -- | Defines the methods expected of a primality-algorithm. class Algorithm algorithm isPrime :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> i -> Bool -- | An ordered list of the Carmichael numbers; -- http://en.wikipedia.org/wiki/Carmichael_number. carmichaelNumbers :: (Algorithm algorithm, NFData i, Integral 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 => 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 :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> i -> 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 :: Algorithm 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 Algorithm squareRootAlgorithm => Algorithm (Algorithm squareRootAlgorithm) instance Defaultable squareRootAlgorithm => Defaultable (Algorithm squareRootAlgorithm) -- |

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 (=+=) :: 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.

(=^) :: (Ring r, Eq r, Integral 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. () :: (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 :: (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) => 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 Data.Functor.fmap, but -- Polynomial isn't an instance of Data.Functor.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 :: (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) => 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 :: (Num c, Num e) => c -> Polynomial c e -- | Constructs an arbitrary first-degree polynomial. mkLinear :: (Num c, Num e) => c -> c -> Polynomial c e -- | Constructs an arbitrary polynomial. mkPolynomial :: (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.

(*=) :: (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 :: 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 :: (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 (Fractional c, Num e, Ord e) => QuotientRing (Polynomial c e) instance (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 -- | Constructs an arbitrary monic polynomial. mkMonicPolynomial :: (Num c, Ord e, 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 (Num c, Num e, Ord e) => QuotientRing (MonicPolynomial c e) instance (Num c, Num e, Ord e, Show e) => Ring (MonicPolynomial c e) -- |

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 the odd 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

-- --

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, and -- omega-numbers.
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 Algorithm algorithm primeFactors :: (Algorithm 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 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.

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 :: (Algorithm 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 :: (Algorithm 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 :: (Algorithm 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 :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> i -> i -- |

A constant, zero-indexed, conceptually infinite, list of the -- small omega numbers, 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 :: (Algorithm 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 :: (Algorithm primeFactorisationAlgorithm, NFData i, Integral 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 Algorithm factorisationAlgorithm => Algorithm (Algorithm factorisationAlgorithm) instance Defaultable (Algorithm factorisationAlgorithm) -- |

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 Algorithm Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Describes a bounded range of, typically integral, -- quantities.
Operations have been defined, on the list of consecutive -- quantities delimited by these two bounds.
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.

module Factory.Data.Bounds -- | Defines a range of consecutive values, bracketed by inclusive -- bounds. type Bounds limit = (limit, limit) -- | True if the specified value is within the inclusive -- Bounds. elem' :: Ord limit => limit -> Bounds limit -> Bool -- | The length of toList. length' :: (Num limit, Ord limit) => Bounds limit -> limit -- | Swap the limits where they were originally reversed, but otherwise do -- nothing. normalise :: Ord limit => Bounds limit -> Bounds limit -- |

Multiplies the consecutive sequence of integers within -- Bounds.
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 => Ratio i -> i -> Bounds i -> i -- | Bisect the bounds at the specified limit; which should be between the -- two existing limits. splitAt' :: (Num limit, Ord limit) => limit -> Bounds limit -> (Bounds limit, Bounds limit) -- | Converts Bounds to a list by enumerating the values. toList :: Enum limit => Bounds limit -> [limit] -- | Accessor. minBound' :: Bounds a -> a -- | Accessor. maxBound' :: Bounds a -> a -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION

-- --

Provides implementations of the class Algorithm.
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.Bounds.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 => i -> i -> i -- | Returns the falling factorial; -- http://mathworld.wolfram.com/FallingFactorial.html fallingFactorial :: Integral 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) => i -> i -> f instance Eq Algorithm instance Read Algorithm instance Show Algorithm instance Algorithm Algorithm instance Defaultable Algorithm -- |

AUTHOR Dr. Alistair Ward
DESCRIPTION Implements Algorithm 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 Algorithm 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 :: (Algorithm squareRootAlgorithm, Algorithm 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 (Algorithm squareRootAlgorithm, Algorithm factorialAlgorithm) => Algorithm (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 :: (Algorithm squareRootAlgorithm, Algorithm factorialAlgorithm) => Series squareRootAlgorithm factorialAlgorithm -- |

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

module Factory.Math.Implementations.Pi.Ramanujan.Classic -- | Defines the parameters of the Ramanujan series. series :: (Algorithm squareRootAlgorithm, Algorithm 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 (Algorithm squareRootAlgorithm, Algorithm factorialAlgorithm) => Algorithm (Algorithm squareRootAlgorithm factorialAlgorithm) instance (Defaultable squareRootAlgorithm, Defaultable factorialAlgorithm) => Defaultable (Algorithm squareRootAlgorithm factorialAlgorithm) -- |

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

module Factory.Math.Statistics -- | Determines the http://en.wikipedia.org/wiki/Mean of the -- supplied numbers. mean :: (Real r, Fractional f) => [r] -> f -- | The number of unordered combinations of r objects taken from -- n; http://en.wikipedia.org/wiki/Combination. nCr :: (Algorithm factorialAlgorithm, Integral i) => factorialAlgorithm -> i -> i -> i -- | The number of permutations of r objects taken from n; -- http://en.wikipedia.org/wiki/Permutations. nPr :: Integral i => i -> i -> i