! " # $ % & ' ( ) * + , - . / 0 123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !!!!!!!!"""""""#########$%%%&&&'''''''''((((((()))))))*++,-...////6Characters used to represent the digits of numbers in (-36 <= base <= 36). "Constant random-access lookup for . Constant reverse-lookup for . h Convert the specified integral decimal quantity, to an alternative base, and represent the result as a . < Both negative decimals and negative bases are permissible.  The conversion to p can only succeed where printable and intelligible characters exist to represent all digits in the chosen base;  which in practice means (-36 <= base <= 36).  Convert the I-representation of a number in the specified base, to a decimal integer. ; Both negative numbers and negative bases are permissible.   *http://mathworld.wolfram.com/DigitSum.html.   &http://en.wikipedia.org/wiki/Digit_sum.  )http://en.wikipedia.org/wiki/Digital_root. -Defines a series corresponding to a specific BBP -formula. HThe constant numerators from which each term in the series is composed. ZGenerates the term-dependent denominators from which each term in the series is composed. RThe ratio by which the sum to infinity of the series, must be scaled to result in Pi. ;The geometric ratio, by which successive terms are scaled.      0Defines the parameters of this specific series.     0Defines the parameters of this specific series.     + 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,  (requiring cross-multiplication), or the list long,  4 is too light-weight for sparking to be productive, 9 therefore it is more likely to be the parallelised deep  evaluation$ of list-elements which saves time. The Chunk-length.  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. 3 CAVEAT: memory-use is proportional to chunk-size. The Chunk-length.    A constant ordered list of the  Fibonacci -numbers.  The subset of , indexed by a prime -number.   ;http://primes.utm.edu/glossary/page.php?sort=FibonacciPrime. "Defines the methods expected of a  factorial -algorithm.  A number of decimal digits. The rate of convergence;  0http://en.wikipedia.org/wiki/Rate_of_convergence. The order of convergence;  0http://en.wikipedia.org/wiki/Rate_of_convergence. Linear1 convergence-rate; which may be qualified by the rate of convergence.  Quadratic convergence-rate. Cubic convergence-rate. Quartic convergence-rate. XThe predicted number of iterations, required to achieve a specific accuracy, at a given order of convergence. 'The precision of the initial estimate. The required precision. F The predicted number of terms which must be extracted from a series, 0 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  convergentB series (in which the error get smaller with successive terms), it's value lies in the range 0 .. 1.   0http://en.wikipedia.org/wiki/Rate_of_convergence. 1The additional number of correct decimal digits. .Promotes the specified number, by a number of .  Reduces a : to the minimal form required for the specified number of  fractional decimal places; 8 irrespective of the number of integral decimal places.  A c 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. BThe number of places after the decimal point, which are required.    $Categorises the various algorithms. $Algorithms from which the digits of Pi slowly drip, one by one.  &http://www.pi314.net/eng/ramanujan.php. ! 2http://en.wikipedia.org/wiki/Borwein%27s_algorithm. " Khttp://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula. #Algorithms based on the Arithmetic-geometric Mean. $# Defines the methods expected of a Pi -algorithm. 0 Most of the implementations naturally return a 0, but the spigot-algorithms naturally produce a [Int];  though representing PiG as a big integer with the decimal point removed is clearly incorrect.  Since representing Pi as either a  or promoted to an *, is inconvenient, an alternative decimal -representation is provided. %Returns the value of Pi as a . &Returns the value of Pi9, promoted by the required precision to form an integer. 'Returns the value of Pi as a decimal .  !"#$%&' $%&'#"!  #"!  !"#$%&'%&' (Returns Pi6, accurate to the specified number of decimal digits. This PiD-algorithm is parameterised by the type of other algorithms to use. 'The number of decimal digits required. ((( )Defines those BBP*-type series which have been implemented. *A  nega-base 2^10 version of the formula. +A base-2^16 version of the formula. )*+)+*)+**+ ,-Defines a series corresponding to a specific Borwein -formula. -./!The expected number of digits of Pi, per term in the series. ,-./,-./,-./-./ 0Returns Pi6, accurate to the specified number of decimal digits. This PiD-algorithm is parameterised by the type of other algorithms to use.  The specific  square-root) algorithm to apply to the above series.  The specific  factorial)-algorithm to apply to the above series. 'The number of decimal digits required. 0001-Defines a series corresponding to a specific  Ramanujan -formula. 23HThe sequence of terms, the sum to infinity of which defines the series. 4TThe ratio by which the sum to infinity of the sequence, must be scaled to result in Pi. 5!The expected number of digits of Pi, per term in the series. 12345123451234523456Returns Pi6, accurate to the specified number of decimal digits. This PiD-algorithm is parameterised by the type of other algorithms to use.  The specific  square-root) algorithm to apply to the above series.  The specific  factorial)-algorithm to apply to the above series. 'The number of decimal digits required. 6667n 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 * (...)))). 89:;<_The width of the spigot-table, required to accurately generate the requested number of digits. = Combines : and ;=, and as a side-effect, expresses the ratio in lowest terms. 789:;<=789:;<=789:;<89:;<=>$Defines a series which converges to Pi. >>>?$Defines a series which converges to Pi. ??? (Coerce the polymorphic type returned by  to our specific requirements. Coerce the polymorphic type & to suit the base used in our series. 0 The type in which all arithmetic is performed. @ A small dynamic range, 32 bits or more, is typically adequate. @:The constant base in which we want the resulting value of Pi to be expressed. } For a digit on one row of the spigot-table, add any numerator carried from the similar calculation one column to the right. i Divide the result of this summation, by the denominator of the base, to get the quotient and remainder.  Determine the quantity to carry to the similar calculation one column to the left, by multiplying the quotient by the numerator of the base.  Fold i, from right to left, over the columns of a row in the spigot-table, continuously checking for overflow. o Release any previously withheld result-digits, after any adjustment for overflow in the current result-digit. m Withhold the current result-digit until the risk of overflow in subsequent result-digits has been assessed.  Call .  Data-row. 0 Multiply the remainders from the previous row.  Zip them with the constant bases, with an addition one stuck on the front to perform the conversion to decimal, to create a new row of the spigot-table.  Call . A Initialises a spigot-table with the row of 9. _ Ensures that the row has suffient terms to accurately generate the required number of digits. A Extracts only those digits which are guaranteed to be accurate. & CAVEAT: the result is returned as an ", i.e. without any decimal point. @A@A@AB Define those Spigot)-algorithms which have been implemented. CA continued fraction discovered by  Rabinowitz and Wagon. DA continued fraction discovered by Gosper. BCDBDCBDCCDE6The list-length beneath which to terminate bisection. F; The ratio of the original list-length at which to bisect. ! CAVEAT: the value can overflow. G5 Reduces a list to a single scalar encapsulated in a ,  using a divide-and-conquer strategy, : bisecting the list and recursively evaluating each part;  9http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.  By choosing a bisectionRatio other than (1 % 2)*, the bisection can be made asymmetrical. d 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  minLengthL integers, and each node of which contains an associative binary operator), B and then collapsed to a scalar, by application of the operators. :The ratio of the original list-length at which to bisect. 6For efficiency, the list will not be bisected, when it')s length has been reduced to this value. The list on which to operate. The resulting scalar. H+ Multiplies the specified list of numbers.  Since the result can be large, GI is used in an attempt to form operands of a similar order of magnitude, N which creates scope for the use of more efficient multiplication-algorithms. :The ratio of the original list-length at which to bisect. 6For efficiency, the list will not be bisected, when it')s length has been reduced to this value. 'The numbers whose product is required. The resulting product. I% Sums the specified list of numbers.  Since the result can be large, GI is used in an attempt to form operands of a similar order of magnitude, N which creates scope for the use of more efficient multiplication-algorithms.  Multiplication is required for the addition of " numbers by cross-multiplication; ; this function is unlikely to be useful for other numbers. :The ratio of the original list-length at which to bisect. 6For efficiency, the list will not be bisected, when it')s length has been reduced to this value. #The numbers whose sum is required. The resulting sum. EFGHIFEGHIEFGHIJMainly for convenience. KJust for convenience. L! 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. MJust for convenience. NK Raise an arbitrary number to the specified positive integral power, using modular arithmetic. 3 Implements exponentiation as a sequence of either squares! or multiplications by the base;   7http://en.wikipedia.org/wiki/Exponentiation_by_squaring.   3http://en.wikipedia.org/wiki/Modular_exponentiation. Base.  Modulus. Result. O 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. q The set of tests, and the valid moduli within each test, are ordered to maximize the rate of failure-detection. P 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. JKLMNOPJLOKMNPJKLMNOP QfThe interface required to iterate, from an estimate of the required value, to the next approximation. RThe value for which the  square-root is required; y. The current estimate; x(n). An improved estimate; x(n+1). SCThe ultimate ratio of successive terms as the iteration converges. T"Defines the methods expected of a  square-root algorithm. U)An initial estimate from which to start. The required precision.  The value for which to find the  square-root. $Returns an improved estimate of the  square-rootc, found using the specified algorithm, accurate to at least the required number of decimal digits. VThe required precision.  The value for which to find the  square-root. Returns an estimate of the  square-rootc, found using the specified algorithm, accurate to at least the required number of decimal digits. WContains an estimate for the  square-root of a value, and its accuracy. X<The result-type; actually, only the concrete return-type of +, stops it being a polymorphic instance of .  Generalise  to operate on any  operand. YUses L-precision floating-point arithmetic, to obtain an initial estimate for the  square-root, and its accuracy. ZA 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. 1 CAVEAT: the magnitude is twice the error in the  square-root. [# if the specified estimate for the  square-root, is precise. \* For a given value and an estimate of its  square-root, 4 returns the number of decimals digits to which the  square-root- is accurate; including the integral digits. A CAVEAT: the result returned for an exact match has been bodged. QRSTUVWXYZ[\ TUVQRSXW\ZY[ QRSRSTUVUVWXYZ[\]Encapsulates both  arithmetic and  geometric means. ^The type of the geometric mean;  +http://en.wikipedia.org/wiki/Geometric_mean. _The type of the arithmetic mean;  ,http://en.wikipedia.org/wiki/Arithmetic_mean. ` Accessor. a Accessor. b0Returns an infinite list which converges on the Arithmetic-geometric mean. c$Returns the bounds within which the ] has been constrained. dChecks that both means# are positive, as required for the geometric mean to be consistently real. ]^_`abcd_^]bc`ad]^_`abcde7Defines the methods expected of a primality-algorithm. fg# 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.   1http://mathworld.wolfram.com/RelativelyPrime.html. h Tests Fermat's Little Theorem? for all applicable values, as a probabilistic primality-test.   6http://en.wikipedia.org/wiki/Fermat%27s_little_theorem.   2http://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. i A Carmichael number is an odd  composite number which satisfies Fermat's little theorem.   .http://en.wikipedia.org/wiki/Carmichael_number.   2http://mathworld.wolfram.com/CarmichaelNumber.html. jAn ordered list of the  Carmichael numbers;  .http://en.wikipedia.org/wiki/Carmichael_number. efghijefjghieffghijk Returns Pi6, accurate to the specified number of decimal digits.  This algorithm is based on the arithmetic-geometric mean of 1 and (1 / sqrt 2), 6 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: V pi = (a[N-1] + g[N-1])^2 / (1 - sum [2^n * (a[n] - g[n])^2]) where n = [0 .. N-1] B => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 - 2*a[n]*g[n] + g[n]^2)]) P => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 + 2*a[n]*g[n] + g[n]^2 - 4*a[n]*g[n])]) B => 4*a[N]^2 / (1 - sum [2^n * ((a[n] + g[n])^2 - 4*a[n]*g[n])]) U => 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)]) kkkl"Defines the available algorithms. mlmlmlmm Does for n, what  does for type  %, in that it makes it an instance of  under addition.    Access the polymorphic payload.   Does for n, what   does for type  %, in that it makes it an instance of  under multiplication.  Access the polymorphic payload. n= Define both the operations applicable to all members of the ring, and its mandatory members.  Minimal definition; o, p, q, r, s. o(Addition of two members; required to be  commutative;  *http://en.wikipedia.org/wiki/Commutativity. pMultiplication of two members. qThe operand required to yield zero under addition;  -http://en.wikipedia.org/wiki/Additive_inverse. rThe identity-member under multiplication;  8http://mathworld.wolfram.com/MultiplicativeIdentity.html. sThe identity-member under addition (AKA zero);  .http://en.wikipedia.org/wiki/Additive_identity. tSubtract the two specified ring -members. uSquare the ring. v Raise a ring2-member to the specified positive integral power. ^ Exponentiation is implemented as a sequence of either squares of, or multiplications by, the ring -member;   7http://en.wikipedia.org/wiki/Exponentiation_by_squaring. w Returns the product of the list of ring -members. x Returns the sum of the list of ring -members. nopqrstuvwx nopqrstuwxv nopqrstuopqrstuvwxyDefines a sub-class of n$, in which division is implemented. zKDivides the first operand by the second, to yield a pair composed from the quotient and the  remainder. { Returns the quotient&, after division of the two specified ys.  Numerator.  Denominator. | Returns the  remainder&, after division of the two specified ys.  Numerator.  Denominator. }  if the two specified ys are  congruent in modulo-arithmetic, where the modulus is a third y.   3http://www.usna.edu/Users/math/wdj/book/node74.html. LHS. RHS.  Modulus. ~ if the second operand divides the first.  Numerator.  Denominator. yz{|}~yz{|}~yzz{|}~$ The type of an arbitrary monomial.  CAVEAT: though a monomialN has an integral power, this contraint is only imposed at the function-level.  Accessor.  Accessor.   if the exponent is both integral and non-negative.  CAVEAT: one can'%t even call this function unless the exponent is integral.  Compares the  exponents of the specified s.  if the  exponents are equal. Multiply the two specified s. Divide the two specified s.  Numerator.  Denominator. Square the specified . Double the specified .  Shift the  coefficient, by the specified amount. The magnitude of the shift.  Shift the exponent, by the specified amount. The magnitude of the shift. Negate the coefficient. Reduce the coefficient using modular arithmetic.  Modulus. Convert the type of the  coefficient.   The type of an arbitrary  univariate polynomial;  actually it'2s 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 :, this is implemented at the function-level, as required. $ The structure permits gaps between  exponents,  in which  coefficientsX are inferred to be zero, thus enabling efficient representation of sparse polynomials.  CAVEAT: the  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.  Accessor. The guts of a . - Transforms the data behind the constructor.  CAVEAT: similar to Data.Functor.fmap, but  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-U the resulting polynomial depending on the nature of the transformation of the data. 8Returns the number of non-zero terms in the polynomial. $Return the highest-degree monomial. Removes terms with a  coefficient of zero.  Sorts into descending order of exponents, groups like exponents, and calls . Constructs an arbitrary zeroeth-degree polynomial, ie. independent of the  indeterminate. Constructs an arbitrary first-degree polynomial.  Gradient.  Constant. Constructs an arbitrary  polynomial.  Constructs a  polynomial with zero terms. Constructs a constant monomial, independent of the  indeterminate.  if all  exponents7 are in the order defined by the specified comparator.  if the  exponents of successive terms are in  ascending order.  if the  exponents of successive terms are in  descending order.  if no term has a  coefficient of zero.  if no term has a  coefficient of zero and the  exponents of successive terms are in  descending order.   if the leading coefficient is one.   =http://en.wikipedia.org/wiki/Monic_polynomial#Classifications.  if there are zero terms.  if there's exactly one term.  if all  exponents are positive integers as required.   if the two specified  polynomials are  congruent in modulo -arithmetic.   <http://planetmath.org/encyclopedia/PolynomialCongruence.html. LHS. RHS.  Modulus.  Return the degree (AKA order ) of the  polynomial.   3http://en.wikipedia.org/wiki/Degree_of_a_polynomial.   2http://mathworld.wolfram.com/PolynomialDegree.html.  Scale-up the specified  polynomial by a constant monomial factor.   2http://en.wikipedia.org/wiki/Scalar_multiplication.  Raise a  polynomial5 to the specified positive integral power, but using modulo -arithmetic. , Whilst one could naively implement this as (x Data.Ring.=^ n)  mJ, this will result in arithmetic operatons on unnecessarily big integers.  The base. 1The exponent to which the base should be raised.  The modulus.  The result. #Reduces all the coefficients using modular arithmetic.  Modulus.  Evaluate the  polynomial at a specific  indeterminate. 3 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 memoizes5 the complete sequence of powers up to the polynomial's degree. The  indeterminate.  The Result. Convert the type of the  coefficients. Defines the ability to divide  polynomials. Makes  Polynomial a n , over the field composed from all possible  coefficients;  ,http://en.wikipedia.org/wiki/Polynomial_ring.   A type of , in which the  leading term is required to have a  coefficient of one. Constructs an arbitrary monic polynomial. ! Describes an  exponential, in terms of its base and exponent.  Accessor.  Accessor.  Construct an ! merely raised to the 1st power. A The value of the resulting exponential is the same as specified base;  -http://en.wikipedia.org/wiki/Identity_element. Evaluate the specified ", returning the resulting number.  if the bases are equal. Raise the specified  to a power.  The operand. 4The power to which the exponential is to be raised.  The result. ,Invert the value, by negating the exponent. " * 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 exponentQ to be integral, these constrains are applied at the function-level as required. ( Sorts a list representing a product of  prime factors by increasing base.  Multiplies  s of similar base.  Multiplies  s of similar base.  Insert a (, 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. R CAVEAT: this is tolerably efficient for the odd insertion; to insert a list, use . 5 Multiplies two lists each representing a product of  prime factors, and sorted by increasing base.  Preserves the sort-order. Invert the product of a list  prime factors, by negating each of the  exponents. 3 Divides two lists, each representing a product of  prime factors, and sorted by increasing base.  Preserves the sort-order.  The list of  prime factors in the  numerator.  The list of  prime factors in the  denominator.  The ratio of  numerator and  denominator , after like  prime factors are cancelled.  Raise the product of a list  prime factors to the specified power. Y CAVEAT: this merely involves raising each element to the specified power; cf. raising a  polynomial to a power. Sum the  exponentsL of the specified list; as required to multiply exponentials with identical base. Multiply a list of  prime factors. The list on which to operate.  The result. # "Defines the methods expected of a  factorisation -algorithm.  The operand ] 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  2) for an even number,  but though a prime-factor greater than the  square-root of the number can exist,  its smaller cofactor3 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)E to filter what can potentially be factored by a given prime-factor. ? 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. > A constant, zero-indexed, conceptually infinite, list of the  power-smoothness of all positive integers.   >http://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers.  Filters !, to derive the constant list of Hamming-numbers.   +http://en.wikipedia.org/wiki/Regular_number.  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) n CAVEAT: checks neither the primality nor the bounds of the specified value; therefore for internal use only.  The number of coprimes7 less than or equal to the specified positive integer.   7http://en.wikipedia.org/wiki/Euler%27s_totient_function.   1http://mathworld.wolfram.com/TotientFunction.html.  AKA EulerPhi. > A constant, zero-indexed, conceptually infinite, list of the  small omega numbers, the number of distinct prime factors; cf.  big omega.   Ghttp://oeis.org/wiki/Omega%28n%29,_number_of_distinct_primes_dividing_n.   6http://mathworld.wolfram.com/DistinctPrimeFactors.html   Lhttp://planetmath.org/encyclopedia/NumberOfDistinctPrimeFactorsFunction.html. $[ 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  8http://rosettacode.org/wiki/Multiplicative_order#Haskell.   1http://en.wikipedia.org/wiki/Multiplicative_order.   5http://mathworld.wolfram.com/MultiplicativeOrder.html. Base.  Modulus. Result. %The algorithms by which  primality-testing has been implemented.  @http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test.  /http://en.wikipedia.org/wiki/AKS_primality_test.   An implementation of the Agrawal-Kayal-Saxena primality-test;  /http://en.wikipedia.org/wiki/AKS_primality_test,  using the Lenstra and  Pomerance algorithm. K CAVEAT: this deterministic algorithm has a theoretical time-complexity of O(log^6),  and therefore can'6t compete with the performance of probabilistic ones.  The formal polynomials9 used in this algorithm, are conceptually different from polynomial functions;  the  indeterminateM and its powers, are merely used to name a sequence of pigeon-holes in which  coefficients are stored, 0 and is never substituted for a specific value. 8 This mind-shift, allows one to introduce concepts like modular arithmetic on polynomials, \ which merely represent an operation on their coefficients and the pigeon-hole in which they' re placed. /Manindra Agrawal, Neeraj Kayal and Nitin Saxena  Ahttp://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. %H. W. Lenstra, Jr. and Carl Pomerance  9http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf. Salembier and Southerington  _http://ece.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf, R. Crandall and J. Papadopoulos  (http://images.apple.com/acg/pdf/aks3.pdf, Andreas Klappenecker  ,http://faculty.cs.tamu.edu/klappi/629/aks.ps, Vibhor Bhatt and G. K. Patra  Ehttp://www.cmmacs.ernet.in/cmmacs/Publications/resch_rep/rrcm0307.pdf, ! Uses the specified base in an attempt to prove the  compositeness of an integer.  This is the opposite of the  Miller Test;  6http://mathworld.wolfram.com/MillersPrimalityTest.html.  If the result is , then the candidate is  composite; regrettably the converse isn't true. < Amongst the set of possible bases, over three-quarters are  witnesses to the compositeness of a  composite candidate, ' the remainder belong to the subset of liars. o In consequence, many false results must be accumulated for different bases, to convincingly identify a prime. Candidate integer. Base. " Repeatedly calls !;, to progressively increase the probability of detecting a  composite number, ? until ultimately the candidate integer is proven to be prime. R Should all bases be tested, then the test is deterministic, but at an efficiency lower& than performing prime-factorisation. r The test becomes deterministic, for any candidate integer, when the number of tests reaches the limit defined by  Eric Bach. b A testing of smaller set of bases, is sufficient for candidates smaller than various thresholds;  )http://primes.utm.edu/prove/prove2_3.html.   8http://en.wikipedia.org/wiki/Miller-Rabin_primality_test.   Chttp://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html   3http://mathworld.wolfram.com/StrongPseudoprime.html.   http://oeis.org/A014233,  http://oeis.org/A006945. &BThe algorithms by which prime-factorisation has been implemented.  +http://en.wikipedia.org/wiki/Trial_division.  <http://en.wikipedia.org/wiki/Fermat%27s_factorization_method. # ;http://en.wikipedia.org/wiki/Dixon%27s_factorization_method. $  ;http://en.wikipedia.org/wiki/Dixon%27s_factorization_method. %  <http://en.wikipedia.org/wiki/Fermat%27s_factorization_method.   <http://mathworld.wolfram.com/FermatsFactorizationMethod.html.   2http://en.wikipedia.org/wiki/Congruence_of_squares.   i = f1 * f2U Assume a non-trivial factorisation, ie. one in which both factors exceed one.  => +i = (larger + smaller) * (larger - smaller)5 Represent the co-factors as a sum and difference.  => i = larger^2 - smaller^2' Which has an integral solution if i is neither even nor a perfect square.  => sqrt (larger^2 - i) = smaller Search for larger), which results in an integral value for smaller.  Given that the smaller factor f2, can't be less than 3 (i isn't even), then the larger f1, can't be greater than (i  3).  So:  (f2 >= 3) && (f1 <= i  3)1 Two equations which can be used to solve for larger.  => (larger - smaller >= 3) && (larger + smaller <= i  3) Add these to eliminate smaller.  => larger < = (i + 9)  6* The upper bound of the search-space. % This algorithm works best when there's a factor close to the  square-root. &5 Decomposes the specified integer, into a product of prime -factors,  using  ;http://mathworld.wolfram.com/DirectSearchFactorization.html, AKA  +http://en.wikipedia.org/wiki/Trial_division. - This works best when the factors are small. ' 4Defines a range of consecutive values, bracketed by  inclusive bounds.  Accessor.  Accessor. 0 if the specified value is within the inclusive . ' if  minBound' exceeds  maxBound' extent. OSwap the limits where they were originally reversed, but otherwise do nothing. [Bisect the bounds at the specified limit; which should be between the two existing limits. The length of .  Converts & to a list by enumerating the values. ( Reduces . to a single integral value encapsulated in a ,  using a divide-and-conquer strategy,  bisecting the bounds' and recursively evaluating each part;  9http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.  By choosing a ratio other than (1 % 2)*, the bisection can be made asymmetrical. c 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. Z This process of recursive bisection, is terminated beneath the specified minimum length,  after which the 3 are expanded into the corresponding list, and the monoid's binary operator is directly folded over it.  One can view this as a  @http://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29,  in which * is exploded into a binary tree-structure . (each leaf of which contains a list of up to  minLengthL integers, and each node of which contains an associative binary operator), B and then collapsed to a scalar, by application of the operators.  The monoid's constructor. 7The ratio of the original span, at which to bisect the . 8For efficiency, the bounds will not be bisected, when it')s length has been reduced to this value. The resulting scalar. 8 Multiplies the consecutive sequence of integers within .  Since the result can be large, (; is used to form operands of a similar order of magnitude, A thus improving the efficiency of the big-number multiplication. !The ratio at which to bisect the . 8For efficiency, the bounds will not be bisected, when it')s length has been reduced to this value. The resulting product. (The algorithms by which  factorial has been implemented. The  prime factors of the  factorialM are extracted, then raised to the appropriate power, before multiplication. The integers from which the  factorial# is composed, are multiplied using Data.Bounds.product'.  Returns the  prime factors , of the  factorial of the specifed integer. F Precisely all the primes less than or equal to the specified integer n, are included in n!; S only the multiplicity of each of these known prime components need be determined.   4http://en.wikipedia.org/wiki/Factorial#Number_theory.  CAVEAT: currently a hotspot. The number, whose  factorial is to be factorised. The base and exponent of each  prime factor in the  factorial, ordered by increasing base (and decreasing exponent). ) The number of times a specific prime, can be factored from the  factorial of the specified integer.  General purpose prime-factorisation has exponential time-complexity,  so use Legendre's Theorem, which relates only to the  prime factors of  factorials.   Ghttp://www.proofwiki.org/wiki/Multiplicity_of_Prime_Factor_in_Factorial. A prime number. ;The integer, the factorial of which the prime is a factor. 7The number of times the prime occurs in the factorial.  Returns the rising factorial;  1http://mathworld.wolfram.com/RisingFactorial.html AThe lower bound of the integer-range, whose product is returned. +The number of integers in the range above.  The result.  Returns the falling factorial;  2http://mathworld.wolfram.com/FallingFactorial.html AThe upper bound of the integer-range, whose product is returned. -The number of integers in the range beneath.  The result. & Returns the ratio of two factorials. J 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  ' then manipulate them using the module Data.PrimeFactors,  and evaluate it using by Data.PrimeFactors.product'. The  numerator. The  denominator. The resulting fraction. ) *%Returns an improved estimate for the  square-rootZ of the specified value, to the required precision, using the supplied initial estimate.. The required precision.  The value for which to find the  square-root. The algorithms by which the  square-root has been implemented.  Lhttp://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Taylor_series.  .http://en.wikipedia.org/wiki/Newton%27s_method.  .http://en.wikipedia.org/wiki/Halley%27s_method.  [http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion.  Vhttp://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Bakhshali_approximation !The number of terms in a series. + Uses continued-fractions#, to iterate towards the principal  square-root$ of the specified positive integer;   Qhttp://en.wikipedia.org/wiki/Solving_quadratic_equations_with_continued_fractions,   Uhttp://en.wikipedia.org/wiki/Generalized_continued_fraction#Roots_of_positive_numbers,   [http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion.   khttp://www.myreckonings.com/Dead_Reckoning/Online/Materials/General%20Method%20for%20Extracting%20Roots.pdf  The convergence  0http://en.wikipedia.org/wiki/Rate_of_convergence of the continued-fraction is merely  1st order (linear). ," The constant coefficients of the  Taylor-series for a  square-root;  Lhttp://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Taylor_series.   ((-1)^n * factorial(2*n)) /$ ((1 - 2*n) * 4^n * factorial(n^2)) . - Returns the  Taylor-series for the  square-root; of the specified value, to any requested number of terms.   Lhttp://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Taylor_series. ) The convergence of the series is merely linear,  in that each term increases the precision, by a constant number of decimal places, equal to the those in the original estimate. v By feeding-back the improved estimate, to form a new series, the order of convergence, on each successive iteration, . becomes proportional to the number of terms;  Terms Convergence  ===== ===========  2 terms /quadratic/  3 terms /cubic/ 9The number of terms of the infinite series, to evaluate. The value for which the  square-root is required. An initial estimate. ./Iterates from the estimated value, towards the  square-rootA, a sufficient number of times to achieve the required accuracy. *Defines the parameters of the Borwein series. + Define those Borwein%-series which have been implemented.  Though currently there'>s only one, provision has been made for the addition of more.  2http://en.wikipedia.org/wiki/Borwein%27s_algorithm. ,Defines the parameters of the  Chudnovsky series. -Defines the parameters of the  Ramanujan series. . Define those  Ramanujan%-series which have been implemented. A variant found by the Chudnovsky brothers. The original version. /Determines the  !http://en.wikipedia.org/wiki/Mean of the supplied numbers. (The number of unordered combinations of r objects taken from n;  (http://en.wikipedia.org/wiki/Combination. 0The total number of items from which to select. "The number of iterms in a sample. The number of combinations. The number of permutations of r objects taken from n;  )http://en.wikipedia.org/wiki/Permutations. 0The total number of items from which to select. !The number of items in a sample. The number of permutations. /0123456789::;<=>?@ABCDEFGHIJKL M N O P Q R @ S T U S @ V W 4 5 X Y S45XZYS45[\]^_::`T@abcdef;ghijklmnop@qrstuvwxRyz{|}~@S@gf;gXk  !!!!!!!!"""""""f#@########$%@%%&@&&'''''''''f(@(((((()@))))))*:+@+,:-:.@..///99999999 9    9999999  "!"""9#%$%%%&&'&(&)&*'+'e(,)-).)/)0)12factory-0.0.0.2Factory.Math.Radix*Factory.Math.Implementations.Pi.BBP.Series+Factory.Math.Implementations.Pi.BBP.Bellard-Factory.Math.Implementations.Pi.BBP.Base65536Factory.Math.SummationFactory.Math.FibonacciFactory.Math.FactorialFactory.Math.PrecisionFactory.Math.Pi2Factory.Math.Implementations.Pi.BBP.Implementation-Factory.Math.Implementations.Pi.BBP.Algorithm.Factory.Math.Implementations.Pi.Borwein.Series6Factory.Math.Implementations.Pi.Borwein.Implementation0Factory.Math.Implementations.Pi.Ramanujan.Series8Factory.Math.Implementations.Pi.Ramanujan.Implementation-Factory.Math.Implementations.Pi.Spigot.Series-Factory.Math.Implementations.Pi.Spigot.Gosper6Factory.Math.Implementations.Pi.Spigot.RabinowitzWagon-Factory.Math.Implementations.Pi.Spigot.Spigot0Factory.Math.Implementations.Pi.Spigot.AlgorithmFactory.Math.DivideAndConquerFactory.Math.PowerFactory.Math.SquareRoot$Factory.Math.ArithmeticGeometricMeanFactory.Math.Primality0Factory.Math.Implementations.Pi.AGM.BrentSalamin-Factory.Math.Implementations.Pi.AGM.AlgorithmFactory.Data.RingFactory.Data.QuotientRingFactory.Data.MonomialFactory.Data.PolynomialFactory.Data.MonicPolynomialFactory.Data.ExponentialFactory.Data.PrimeFactorsFactory.Math.PrimeFactorisation Factory.Math.MultiplicativeOrder&Factory.Math.Implementations.Primality/Factory.Math.Implementations.PrimeFactorisationFactory.Data.Bounds&Factory.Math.Implementations.Factorial'Factory.Math.Implementations.SquareRoot3Factory.Math.Implementations.Pi.Borwein.Borwein19931Factory.Math.Implementations.Pi.Borwein.Algorithm4Factory.Math.Implementations.Pi.Ramanujan.Chudnovsky1Factory.Math.Implementations.Pi.Ramanujan.Classic3Factory.Math.Implementations.Pi.Ramanujan.AlgorithmFactory.Math.StatisticstoBasefromBasedigitSum digitalRootSeriesMkSeries numeratorsgetDenominatorsseriesScalingFactorbaseseriessum'sumR'sumR fibonacciprimeIndexedFibonacci Algorithm factorial DecimalDigitsConvergenceRateConvergenceOrderlinearConvergencequadraticConvergencecubicConvergencequarticConvergencegetIterationsRequiredgetTermsRequiredpromotesimplifyCategorySpigot RamanujanBorweinBBPAGMopenRopenIopenSBellard Base65536termsconvergenceRategetSeriesScalingFactor coefficientsbaseNumeratorsbaseDenominatorsnTermsbasesdecimalRabinowitzWagonGosper MinLengthBisectionRatiodivideAndConquerproduct'squarecube squaresFromcubeRoot raiseModulomaybeSquareNumberisPerfectPowerIteratorstepconvergenceOrdersquareRootFrom squareRootEstimateResult getEstimategetDiscrepancy isPrecise getAccuracy GeometricMeanArithmeticMeangetArithmeticMeangetGeometricMean convergeToAGMspreadisValidisPrime areCoprimeisFermatWitnessisCarmichaelNumbercarmichaelNumbers BrentSalaminRing=+==*=additiveInversemultiplicativeIdentityadditiveIdentity=-==^ QuotientRingquotRem'quot'rem'areCongruentModulo isDivisibleByMonomialgetCoefficient getExponent isMonomial<=>=~<*>doubleshiftCoefficient shiftExponentnegateCoefficientmod'realCoefficientToFrac PolynomialliftgetLeadingTerm normalise mkConstantmkLinear mkPolynomialzerooneinAscendingOrderinDescendingOrder isNormalisedisMonicisZero isPolynomial getDegree*=evaluaterealCoefficientsToFracMonicPolynomial getPolynomialmkMonicPolynomial ExponentialgetBase rightIdentity<^invertFactorsreduceinsert'>*<>/<>^ primeFactorsmaxBoundPrimeFactor smoothnesspowerSmoothnessregularNumbersprimePowerTotient eulersTotientomegamultiplicativeOrder MillerRabinAKS TrialDivision FermatsMethodBounds minBound' maxBound'elem'splitAt'length'toListPrimeFactorisation BisectionrisingFactorialfallingFactorial!/! TaylorSeriesNewtonRaphsonIteration HalleysMethodContinuedFractionBakhshaliApproximationTerms Borwein1993 ChudnovskyClassicmeannCrnPrdigitsencodesdecodesGHC.BaseStringghc-prim GHC.TypesCharGHC.RealRational Data.Listsum integer-gmpGHC.Integer.TypeInteger CoefficientsPi PreDigitsQuotRemquotRemBaseRatioI getQuotient getRemaindercarryAndDivideprocessColumnsmkRow Data.MonoidMonoid FractionalrSqrt GHC.FloatsqrtRealDoubleGHC.BoolTrueSumGHC.NumNumMkSumgetSumProduct MkProduct getProductIntegral MonomialList MkPolynomialgetMonomialListpruneCoefficientsinOrder isReducedmod$fQuotientRingPolynomial$fRingPolynomialMkMonicPolynomial reduceSorted sumExponentsdiv isPrimeByAKSwitnessesCompositenessisPrimeByMillerRabin DixonsMethodfactoriseByDixonsMethodfactoriseByFermatsMethodfactoriseByTrialDivision isReversedprimeMultiplicityProblemSpecificationsquareRootByContinuedFractiontaylorSeriesCoefficientssquareRootByTaylorSeriessquareRootByIteration