I$            ! " # $ % & ' ( ) * + , - . / 0 123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"""""###########$$$$$$%%%%%%%%%%%%%%%&&&&&&&&&&&&&&&&&&&&&&&&'''((((((((((((())))))))))********+++++++,,,,,,,-../011122222223333 3 3 3 4 4444444445666788888 8!9"9#99 Safe-Inferedh 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.  Safe-Infered"Defines the methods expected of a  prime-number generator. ) Returns the constant list, defining the  Primorial.   &http://en.wikipedia.org/wiki/Primorial.   +http://mathworld.wolfram.com/Primorial.html. 0Returns the constant, infinite, list of primes.  Safe-Infered+ 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.  Sums a list of rational type numbers.  CAVEAT: though faster than 'W, this algorithm has poor space-complexity, making it unsuitable for unrestricted use.  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.  The Chunk-length.     Safe-Infered -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.       Safe-Infered0Defines the parameters of this specific series.  Safe-Infered0Defines the parameters of this specific series.  Safe-InferedMainly for convenience. Just for convenience. ! 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. Just for convenience. K 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.  Lower bound.  [(n, n^2)] . Base.  Modulus. Result.  Safe-Infered Returns  (Just . sqrt) if the specified integer is a  square number (AKA perfect square).   *http://en.wikipedia.org/wiki/Square_number.   .http://mathworld.wolfram.com/SquareNumber.html.  (Math.Power.square . sqrt)[ is expensive, so the modulus of the operand is tested first, in an attempt to prove it isn't a perfect square. q The set of tests, and the valid moduli within each test, are ordered to maximize the rate of failure-detection.  An integer (> 1)- which can be expressed as an integral power (> 1) of a smaller natural number.  CAVEAT: zero and one& are normally excluded from this set.   *http://en.wikipedia.org/wiki/Perfect_power.   .http://mathworld.wolfram.com/PerfectPower.html. $ A generalisation of the concept of perfect squares, in which only the exponent '2' is significant.   Safe-Infered?Defines the methods expected of a primality-testing algorithm. (# 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.  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.  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. An ordered list of the  Carmichael numbers;  .http://en.wikipedia.org/wiki/Carmichael_number.   Safe-Infered For each prime3, the infinite list of candidates greater than its square, ! is filtered for indivisibility;  Rhttp://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division. % CAVEAT: though one can easily add a :;, it proved counterproductive.   Safe-Infered ' Merely to enhance self-documentation.  CAVEAT: whilst ! and  # can be independent types for both % and &, they interact for other hyper-exponents. !' Merely to enhance self-documentation. # CAVEAT: whilst it may appear that ! could be non-), the recursive definition for hyper-exponents above &, prevents this. ) Returns the  power-tower of the specified base;  ,http://mathworld.wolfram.com/PowerTower.html.  A synonym for  tetration;   &http://en.wikipedia.org/wiki/Tetration,   2http://www.tetration.org/Fractals/Atlas/index.html. *The hyperoperation -sequence;  +http://en.wikipedia.org/wiki/Hyperoperation. +The Ackermann-Peter -function;  Ahttp://en.wikipedia.org/wiki/Ackermann_function#Ackermann_numbers. ,True if !hyperoperation base hyperExponent' has the same value for each specified rank. !"#$%&'()*+, !"#$%&'()*+, ! "('&%$#*+), !"#$%&'()*+,  Safe-Infered-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. -.-.-.-.  Safe-Infered/"Defines the methods expected of a  factorial -algorithm. /0/0/0/0 Safe-Infered 1A number of decimal digits. 2The rate of convergence;  0http://en.wikipedia.org/wiki/Rate_of_convergence. 3The order of convergence;  0http://en.wikipedia.org/wiki/Rate_of_convergence. 4Linear1 convergence-rate; which may be qualified by the rate of convergence. 5 Quadratic convergence-rate. 6Cubic convergence-rate. 7Quartic convergence-rate. 8XThe predicted number of iterations, required to achieve a specific accuracy, at a given order of convergence. 9F 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. :.Promotes the specified number, by a number of 1. ; 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. 12345678'The precision of the initial estimate. The required precision. 91The additional number of correct decimal digits. :;BThe number of places after the decimal point, which are required. 123456789:; 321456789:; 123456789:; Safe-Infered<fThe interface required to iterate, from an estimate of the required value, to the next approximation. ?"Defines the methods expected of a  square-root algorithm. BContains an estimate for the  square-root of a value, and its accuracy. C<The result-type; actually, only the concrete return-type of ;+, stops it being a polymorphic instance of *. DUses +L-precision floating-point arithmetic, to obtain an initial estimate for the  square-root, and its accuracy. E# 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. F'True if the specified estimate for the  square-root, is precise. G* 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. <=The value for which the  square-root is required; y. The current estimate; x(n). An improved estimate; x(n+1). >CThe ultimate ratio of successive terms as the iteration converges. ?@)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. AThe 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. BCDEFG <=>?@ABCDEFG ?@A<=>CBGEDF<=>?@ABCDEFG Safe-InferedH$Categorises the various algorithms. I$Algorithms from which the digits of Pi slowly drip, one by one. J &http://www.pi314.net/eng/ramanujan.php. K 2http://en.wikipedia.org/wiki/Borwein%27s_algorithm. L Khttp://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula. MAlgorithms based on the Arithmetic-geometric Mean. N# 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. HIJKLMNOReturns the value of Pi as a &. PReturns the value of Pi9, promoted by the required precision to form an integer. QReturns the value of Pi as a decimal $. -. HIJKLMNOPQ NOPQHMLKJIHMLKJINOPQ-. Safe-InferedRReturns Pi6, accurate to the specified number of decimal digits. RThis PiD-algorithm is parameterised by the type of other algorithms to use. 'The number of decimal digits required. RRR Safe-InferedSDefines those BBP*-type series which have been implemented. TA  nega-base 2^10 version of the formula. UA base-2^16 version of the formula. STU/0STUSUTSUT/0 Safe-InferedV-Defines a series corresponding to a specific Borwein -formula. Y!The expected number of digits of Pi, per term in the series. VWXYVWXYVWXYVWXY Safe-InferedZReturns Pi6, accurate to the specified number of decimal digits. ZThis 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. ZZZ Safe-Infered[-Defines a series corresponding to a specific  Ramanujan -formula. ]HThe sequence of terms, the sum to infinity of which defines the series. ^TThe ratio by which the sum to infinity of the sequence, must be scaled to result in Pi. _!The expected number of digits of Pi, per term in the series. [\]^_[\]^_[\]^_[\]^_ Safe-Infered`Returns 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. ``` Safe-Inferedan 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 * (...)))). f_The width of the spigot-table, required to accurately generate the requested number of digits. g Combines d and e=, and as a side-effect, expresses the ratio in lowest terms. abcdefgabcdefgabcdefgabcdefg Safe-Inferedh$Defines a series which converges to Pi. hhhh Safe-Inferedi$Defines a series which converges to Pi. iiii Safe-Inferedj:The constant base in which we want the resulting value of Pi to be expressed. k Initialises a spigot-table with the row of c. _ 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. jkjkjkjk Safe-Inferedl Define those Spigot)-algorithms which have been implemented. mA continued fraction discovered by  Rabinowitz and Wagon. nA continued fraction discovered by Gosper. lmn12lmnlnmlnm12 Safe-InferedoEncapsulates both  arithmetic and  geometric means. pThe type of the geometric mean;  +http://en.wikipedia.org/wiki/Geometric_mean. qThe type of the arithmetic mean;  ,http://en.wikipedia.org/wiki/Arithmetic_mean. r Accessor. s Accessor. t0Returns an infinite list which converges on the Arithmetic-geometric mean. u$Returns the bounds within which the o has been constrained. vChecks that both means# are positive, as required for the geometric mean to be consistently real. opqrstuvopqrstuvqpotursvopqrstuv Safe-Inferedw 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)]) wwww Safe-Inferedx"Defines the available algorithms. xy34xyxyxy34 Safe-Infered z!Couples a candidate prime with a  rolling wheel!, to define the distance rolled. {The size of the wheel>, measured by the number of primes from which it is composed. |GAn infinite increasing sequence, of the multiples of a specific prime. } A conceptual wheel", with irregularly spaced spokes;  Khttp://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Prime_Wheels. K On being rolled, the trace of the spokes, identifies candidates which are coprime to those primes from which the wheel was composed. P One can alternatively view this as a set of vertical nested rings, each with a prime circumference$, and touching at its lowest point.  Each has a single mark on its  circumference1, which when rolled identifies multiples of that  circumference.  When the complete set is rolled, from the state where all marks are coincident, all multiples of the set of primes, are traced. A CAVEAT: The distance required to return to this state (the wheel's  circumference,), grows rapidly with the number of primes:  ; zip [0 ..] . scanl (*) 1 $ [2,3,5,7,11,13,17,19,23,29,31] ~ [(0,1),(1,2),(2,6),(3,30),(4,210),(5,2310),(6,30030),(7,510510),(8,9699690),(9,223092870),(10,6469693230),(11,200560490130)] D The number of spokes also grows rapidly with the number of primes: F zip [0 ..] . scanl (*) 1 . map pred $ [2,3,5,7,11,13,17,19,23,29,31] w [(0,1),(1,1),(2,2),(3,8),(4,48),(5,480),(6,5760),(7,92160),(8,1658880),(9,36495360),(10,1021870080),(11,30656102400)] ~AAccessor: the ordered sequence of initial primes, from which the wheel was composed. BAccessor: the sequence of spoke-gaps, the sum of which equals its  circumference. The  circumference of the specified }. &The number of spokes in the specified }. : The optimal number of low primes from which to build the wheel,, grows with the number of primes required;  the  circumference should be approximately the  square-root9 of the number of integers it will be required to sieve. L CAVEAT: one greater than this is returned, which empirically seems better. Smart constructor for a wheel* from the specified number of low primes. : The optimal number of low primes from which to build the wheel,, grows with the number of primes required;  the  circumference should be approximately the  square-root9 of the number of integers it will be required to sieve. , The sequence of gaps between spokes on the wheel is symmetrical under reflection;  though two values lie on the axis, that aren't part of this symmetry. Eg:   nPrimes Gaps  ====== ====  0 [1]  1 [2] --The terminal gap for all subsequent wheels is '2'; [(succ circumference `mod` circumference) - (pred circumference `mod` circumference)]. I 2 [4,2] --Both points are on the axis, so the symmetry isn't yet clear.  3 [6,4,2,4,2,4,6,2] g 4 [10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2] ZExploitation of this property has proved counter-productive, probably because it requires strict evaluation, @ exposing the user to the full cost of inadvertently choosing a wheel0, which in practice, is rotated less than once. (Generates a new candidate prime, from a  rolling wheel, and the current candidate. RGenerate an infinite, increasing sequence of candidate primes, from the specified wheel. ? Generates multiples of the specified prime, starting from its square, E skipping those multiples of the low primes from which the specified } was composed,  and which therefore, the wheel won't generate as candidates. Eg: $ Prime Rotating PrimeWheel 3 Output $ ===== ===================== ====== ; 7 [4,2,4,2,4,6,2,6] [49,77,91,119,133,161,203,217,259 ..] ; 11 [2,4,2,4,6,2,6,4] [121,143,187,209,253,319,341,407 ..] ? 13 [4,2,4,6,2,6,4,2] [169,221,247,299,377,403,481,533,559 ..] z{|}~"The number to square and multiply A  rolling wheel0, the track of which, delimits the gaps between coprime candidates. z{|}~ z{|}~ z{|}~  Safe-Infered Generates the constant bounded list of  prime-numbers.   /http://cr.yp.to/papers/primesieves-19990826.pdf @Other implementations effectively use a hard-coded value either 2 or 3, but 6 seems better. The maximum prime required. The bounded list of primes. ! Safe-Infered A refinement of the Sieve Of Eratosthenes4, which pre-sieves candidates, selecting only those coprime7 to the specified short sequence of low prime-numbers. ; The short sequence of initial primes are represented by a }, % of parameterised, but static, size;  0http://en.wikipedia.org/wiki/Wheel_factorization. Z The algorithm requires one to record multiples of previously discovered primes, allowing  composite, candidates to be eliminated by comparison.  Because each list of multiples, starts with the square+ of the prime from which it was generated,  the vast majority will be larger than the maximum prime ultimately demanded, and the effort of constructing and storing this list, is consequently wasted. \ Many implementations solve this, by requiring specification of the maximum prime required, O thus allowing the construction of redundant lists of multiples to be avoided.  This implementation doesn'4t impose that constraint, leaving a requirement for rapid storage,  which is supported by  appending the list of prime-multiples, to a queue. = If a large enough candidate is ever generated, to match the head of the list of prime-multiples,  at the head of this queue, then the whole list( of prime-multiples is dropped from the queue,  but the tail of this listn of prime-multiples, for which there is now a high likelyhood of a subsequent match, must now be re-recorded.  A queue doesn't support efficient random  insertion, so a 5) is used for these subsequent multiples. + This solution is faster than just using a Data.PQueue.Min.  CAVEAT: has linear O(n) space-complexity. " Safe-Infered6The list-length beneath which to terminate bisection. ; The ratio of the original list-length at which to bisect. ! CAVEAT: the value can overflow. 5 Reduces a list to a single scalar encapsulated in a 6,  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. + Multiplies the specified list of numbers.  Since the result can be large, I 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. % Sums the specified list of numbers.  Since the result can be large, I 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 list on which to operate. The resulting scalar. :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. :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. # Safe-Infered= Define both the operations applicable to all members of the ring, and its mandatory members.  Minimal definition; , , , , .  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.  Returns the product of the list of ring -members.  Returns the sum of the list of ring -members. (Addition of two members; required to be  commutative;  *http://en.wikipedia.org/wiki/Commutativity. Multiplication of two members. The operand required to yield zero under addition;  -http://en.wikipedia.org/wiki/Additive_inverse. The identity-member under multiplication;  8http://mathworld.wolfram.com/MultiplicativeIdentity.html. The identity-member under addition (AKA zero);  .http://en.wikipedia.org/wiki/Additive_identity. Subtract the two specified ring -members. Square the ring. 78 78$ Safe-InferedDefines a sub-class of $, in which division is implemented.  Returns the quotient&, after division of the two specified s.  Returns the  remainder&, after division of the two specified s.  ( if the two specified s are  congruent in modulo-arithmetic, where the modulus is a third .   3http://www.usna.edu/Users/math/wdj/book/node74.html. True if the second operand divides the first. KDivides the first operand by the second, to yield a pair composed from the quotient and the  remainder.  Numerator.  Denominator.  Numerator.  Denominator. LHS. RHS.  Modulus.  Numerator.  Denominator. % Safe-Infered$ 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.  True if the  exponents are equal. Multiply the two specified s. Divide the two specified s. Square the specified . Double the specified .  Shift the  coefficient, by the specified amount.  Shift the exponent, by the specified amount. Negate the coefficient. Reduce the coefficient using modular arithmetic. Convert the type of the  coefficient.  Numerator.  Denominator. The magnitude of the shift. The magnitude of the shift.  Modulus. & Safe-Infered 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 9 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. - Transforms the data behind the constructor.  CAVEAT: similar to <=, but  isn't an instance of <>& 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.  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. +Smart constructor. Constructs an arbitrary  polynomial.  Constructs a  polynomial with zero terms. Constructs a constant monomial, independent of the  indeterminate.  True if the  exponents of successive terms are in  ascending order.  True if the  exponents of successive terms are in  descending order. True 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. True if there are zero terms.  True if there's exactly one term.  True if all  exponents are positive integers as required.  ( if the two specified  polynomials are  congruent in modulo -arithmetic.   <http://planetmath.org/encyclopedia/PolynomialCongruence.html.  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. #Reduces all the coefficients using modular arithmetic.  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. Convert the type of the  coefficients. <Defines the ability to divide  polynomials. =Makes  Polynomial a  , over the field composed from all possible  coefficients;  ,http://en.wikipedia.org/wiki/Polynomial_ring.  Gradient.  Constant. LHS. RHS.  Modulus.  The base. 1The exponent to which the base should be raised.  The modulus.  The result.  Modulus. The  indeterminate.  The Result. <=<=' Safe-Infered A type of , in which the  leading term is required to have a  coefficient of one. +Smart constructor. Constructs an arbitrary monic polynomial. >?>?( Safe-Infered =Defines a closed (inclusive) interval of consecutive values.  Accessor.  Accessor. Construct the unsigned closed unit-interval;  *http://en.wikipedia.org/wiki/Unit_interval.  Construct an interval from a bounded type.  Construct an interval from a single value. Shift of both  end-points of the interval by the specified amount. BTrue if the specified value is within the inclusive bounds of the interval. True if  exceeds  extent.  Swap the  end-points@ where they were originally reversed, but otherwise do nothing.  Bisect the interval at the specified  end-point+; which should be between the two existing  end-points.  Converts & to a list by enumerating the values. ) CAVEAT: produces rather odd results for *4 types, but no stranger than considering such types @erable. 8 Multiplies the consecutive sequence of integers within .  Since the result can be large, A; is used to form operands of a similar order of magnitude, A thus improving the efficiency of the big-number multiplication. $The magnitude of the require shift. The interval to be shifted. !The ratio at which to bisect the . For efficiency, the interval will not be bisected, when it')s length has been reduced to this value. The resulting product. ) Safe-Infered  Describes a !discrete probability-distribution;  Uhttp://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions.  Describes a #continuous probability-distribution;  Whttp://en.wikipedia.org/wiki/List_of_probability_distributions#Continuous_distributions.  Defines a Normal -distribution with a particular mean and variance;  0http://en.wikipedia.org/wiki/Normal_distribution.  Defines a Uniform-distribution within a closed interval;  1http://en.wikipedia.org/wiki/Uniform_distribution.  Converts a pair of independent uniformly distributed random numbers, within the  semi-closed  unit interval (0 .. 1],  to a pair of independent normally distributed! random numbers, of standardized mean=0, and variance=1.   9http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform. , Uses the supplied random-number generator, . to generate a conceptually infinite list, of normally distributed# random numbers, with standardized mean=0, and variance=1.   0http://en.wikipedia.org/wiki/Normal_distribution,  4http://mathworld.wolfram.com/NormalDistribution.html. _ Generates a random sample-population, with the specified continuous probability-distribution.  When a Normal distribution is requested, ? the generated population will only tend towards the requested mean and variance0 of, as the sample-size tends towards infinity.  Whilst one could arrange for these criteria to be precisely met for any sample-size, the sample would lose a degree of randomness as a result. , Uses the supplied random-number generator, P to generate a conceptually infinite list, of random integers conforming to the Poisson distribution (mean =lambda, variance =lambda).   1http://en.wikipedia.org/wiki/Poisson_distribution.  CAVEAT: - uses an algorithm by Knuth, which having a linear time-complexity in lambda, can be intolerably slow;  also, the term exp $ negate lambda, underflows for large lambda;  so for large lambda., this implementation returns the appropriate , which is similar for large lambda. \Generates a random sample-population, with the specified discrete probability-distribution.  Independent, uniformly distributed* random numbers, which must be within the semi-closed unit interval, (0, 1].  Independent, normally distributed# random numbers, with standardized mean=0 and variance=1. number of items. A generator of uniformly distributed random numbers. /Defines the required approximate value of both mean and variance. number of items. A generator of uniformly distributed random numbers. BC BC* Safe-Infered 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.  True if the bases are equal. Raise the specified  to a power. ,Invert the value, by negating the exponent.  The operand. 4The power to which the exponential is to be raised.  The result. + Safe-Infered* 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.  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. S CAVEAT: this is tolerably efficient for sporadic 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. 3 Divides two lists, each representing a product of  prime factors, and sorted by increasing base.  Preserves the sort-order.  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. Multiply a list of  prime factors.  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. The list on which to operate.  The result. , Safe-InferedThe 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.Interval.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.  Returns the rising factorial;  1http://mathworld.wolfram.com/RisingFactorial.html  Returns the falling factorial;  2http://mathworld.wolfram.com/FallingFactorial.html & 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 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). AThe lower bound of the integer-range, whose product is returned. +The number of integers in the range above.  The result. AThe upper bound of the integer-range, whose product is returned. -The number of integers in the range beneath.  The result. The  numerator. The  denominator. The resulting fraction. DEDE- Safe-InferedDefines the parameters of the Borwein series. . Safe-Infered 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. FGFG/ Safe-InferedDefines the parameters of the  Chudnovsky series. 0 Safe-InferedDefines the parameters of the  Ramanujan series. 1 Safe-Infered Define those  Ramanujan%-series which have been implemented. A variant found by the Chudnovsky brothers. The original version. HIHI2 Safe-Infered Determines the mean of the specified numbers;  !http://en.wikipedia.org/wiki/Mean. - Should the caller define the result-type as &-, then it will be free from rounding-errors.  Determines the exact variance of the specified numbers;  %http://en.wikipedia.org/wiki/Variance. - Should the caller define the result-type as &-, then it will be free from rounding-errors. Determines the standard-deviation of the specified numbers;  /http://en.wikipedia.org/wiki/Standard_deviation.  Determines the average absolute deviation of the specified numbers;  Jhttp://en.wikipedia.org/wiki/Absolute_deviation#Average_absolute_deviation. - Should the caller define the result-type as &-, then it will be free from rounding-errors. Determines the coefficient-of-variance of the specified numbers;  5http://en.wikipedia.org/wiki/Coefficient_of_variation. The number of unordered  combinations of r objects taken from n;  (http://en.wikipedia.org/wiki/Combination. 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 combinations. 0The total number of items from which to select. !The number of items in a sample. The number of permutations. 3 Safe-InferedThe 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.    JKL         JKL4 Safe-Infered  "Defines the methods expected of a  factorisation -algorithm. ] 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 M 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 then 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. Q CAVEAT: suffers from rounding-errors, though no consequence has been witnessed. ? 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 (i.e. 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. 0 A constant, conceptually infinite, list of the  square-free numbers, i.e. those which aren't divisible by any perfect square.   0http://en.wikipedia.org/wiki/Square-free_integer.    The operand          5 Safe-Infered[ 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. 6 Safe-InferedThe 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. NONO7 Safe-Infered4 For each candidate, confirm indivisibility, by all primes smaller than its  square-root. - The candidates to sieve, are generated by a }, % of parameterised, but static, size;  0http://en.wikipedia.org/wiki/Wheel_factorization. 8 Safe-Infered>The implemented methods by which the primes may be generated. P.  For each prime3, the infinite list of candidates greater than its square", is filtered for indivisibility;  Rhttp://www.haskell.org/haskellwiki/Prime_numbers#Turner.27s_sieve_-_Trial_division. 3For each candidate, confirm indivisibility, by all primes smaller than its  square-root, optimised using a }. The Sieve of Eratosthenes ( 2http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), optimised using a }.  The Sieve of Atkin, optimised using a }@ of optimal size, for primes up to the specified maximum bound;  +http://en.wikipedia.org/wiki/Sieve_of_Atkin.  QR   QR9 Safe-Infered!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. !"#ST!"#!#"!#"STU?@ABCDEFGHIJKLMNOOPQRSTUV C W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k C lmnopqrstuvwxyzC{|}~CIJIJIJOO; !"""""F########P###F$$$$$$%%%%%%%%%P%%%%%%&&&&&&&&&&&&&&&&&&&&&T&&&'''((((((((((((())))))))))********+++++++,,,,, , , -O.. /O0O11 1222222233333334C444444 4!4"4#5$66%6&7'88(8)8*8+8,99*9-N./012N34N56017N38N3901:;<=>?@A@A@ABCDNEF#G#H&I&JN3K&L&M'N'ONPQ()R)S,@,A.@.A1@1A3T3@3AN3U6@6AVWX8@8A9@9AYfactory-0.2.0.4Factory.Math.RadixFactory.Math.PrimesFactory.Math.Summation*Factory.Math.Implementations.Pi.BBP.Series+Factory.Math.Implementations.Pi.BBP.Bellard-Factory.Math.Implementations.Pi.BBP.Base65536Factory.Math.PowerFactory.Math.PerfectPowerFactory.Math.Primality0Factory.Math.Implementations.Primes.TurnersSieveFactory.Math.HyperoperationFactory.Math.FibonacciFactory.Math.FactorialFactory.Math.PrecisionFactory.Math.SquareRootFactory.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.Algorithm$Factory.Math.ArithmeticGeometricMean0Factory.Math.Implementations.Pi.AGM.BrentSalamin-Factory.Math.Implementations.Pi.AGM.AlgorithmFactory.Data.PrimeWheel0Factory.Math.Implementations.Primes.SieveOfAtkin7Factory.Math.Implementations.Primes.SieveOfEratosthenesFactory.Math.DivideAndConquerFactory.Data.RingFactory.Data.QuotientRingFactory.Data.MonomialFactory.Data.PolynomialFactory.Data.MonicPolynomialFactory.Data.IntervalFactory.Math.ProbabilityFactory.Data.ExponentialFactory.Data.PrimeFactors&Factory.Math.Implementations.Factorial3Factory.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.Statistics'Factory.Math.Implementations.SquareRootFactory.Math.PrimeFactorisation Factory.Math.MultiplicativeOrder&Factory.Math.Implementations.Primality1Factory.Math.Implementations.Primes.TrialDivision-Factory.Math.Implementations.Primes.Algorithm/Factory.Math.Implementations.PrimeFactorisationData.PrimeWheel PrimeWheel Data.FunctorfmapFunctortoBasefromBasedigitSum digitalRoot Algorithmicprimes primorialsum'sumR'sumRSeriesMkSeries numeratorsgetDenominatorsseriesScalingFactorbaseseriessquarecube squaresFromcubeRoot raiseModulomaybeSquareNumberisPerfectPowerisPrime areCoprimeisFermatWitnessisCarmichaelNumbercarmichaelNumbers turnersSieve HyperExponentBase successionadditionmultiplicationexponentiation tetration pentationhexation powerTowerhyperoperationackermannPeterareCoincidental fibonacciprimeIndexedFibonacci factorial DecimalDigitsConvergenceRateConvergenceOrderlinearConvergencequadraticConvergencecubicConvergencequarticConvergencegetIterationsRequiredgetTermsRequiredpromotesimplifyIteratorstepconvergenceOrdersquareRootFrom squareRootEstimateResult getEstimategetDiscrepancy isPrecise getAccuracyCategorySpigot RamanujanBorweinBBPAGMopenRopenIopenS AlgorithmBellard Base65536termsconvergenceRategetSeriesScalingFactor coefficientsbaseNumeratorsbaseDenominatorsnTermsbasesdecimalRabinowitzWagonGosper GeometricMeanArithmeticMeangetArithmeticMeangetGeometricMean convergeToAGMspreadisValid BrentSalaminDistanceNPrimesPrimeMultiplesgetPrimeComponents getSpokeGapsgetCircumference getSpokeCountestimateOptimalSize mkPrimeWheelrotaterollgenerateMultiples sieveOfAtkinsieveOfEratosthenes MinLengthBisectionRatiodivideAndConquerproduct'Ring=+==*=additiveInversemultiplicativeIdentityadditiveIdentity=-==^ QuotientRingquotRem'quot'rem'areCongruentModulo isDivisibleByMonomialgetCoefficient getExponent isMonomial<=>=~<*>doubleshiftCoefficient shiftExponentnegateCoefficientmod'realCoefficientToFrac PolynomialliftgetLeadingTerm normalise mkConstantmkLinear mkPolynomialzerooneinAscendingOrderinDescendingOrder isNormalisedisMonicisZero isPolynomial getDegree*=evaluaterealCoefficientsToFracMonicPolynomial getPolynomialmkMonicPolynomialInterval getMinBound getMaxBoundclosedUnitInterval mkBounded preciselyshiftelem' isReversedsplitAt'toListDiscreteDistributionPoissonDistributionContinuousDistributionNormalDistributionUniformDistributionboxMullerTransform&generateStandardizedNormalDistributiongenerateContinuousPopulationgeneratePoissonDistributiongenerateDiscretePopulation ExponentialgetBase rightIdentity<^invertFactorsreduceinsert'>*<>/<>^PrimeFactorisation Bisection primeFactorsrisingFactorialfallingFactorial!/! Borwein1993 ChudnovskyClassicgetMean getVariancegetStandardDeviationgetAverageAbsoluteDeviationgetCoefficientOfVariancenCrnPr TaylorSeriesNewtonRaphsonIteration HalleysMethodContinuedFractionBakhshaliApproximationTermsmaxBoundPrimeFactor smoothnesspowerSmoothnessregularNumbersprimePowerTotient eulersTotientomega squareFreemultiplicativeOrder MillerRabinAKS trialDivision WheelSieve TurnersSieve TrialDivisionSieveOfEratosthenes SieveOfAtkin FermatsMethodGHC.BaseStringghc-prim GHC.TypesCharGHC.RealRational Data.ListsumTrueIntegral FractionalDouble integer-gmpGHC.Integer.TypeInteger$fAlgorithmicCategory$fDefaultableCategory$fAlgorithmicAlgorithm$fDefaultableAlgorithmcontainers-0.4.2.1Data.MapMap Data.MonoidMonoid $fMonoidSum$fMonoidProduct MonomialListpruneCoefficientsmod$fQuotientRingPolynomial$fRingPolynomial$fQuotientRingMonicPolynomial$fRingMonicPolynomialGHC.EnumEnum#$fSelfValidatorDiscreteDistribution%$fSelfValidatorContinuousDistribution$fIteratorAlgorithmdivprimes-0.2.1.0Data.Numbers.Primes wheelSieve