!"#$%&'()*+,-./0123456789:;<= > ? @ A B C D E F G H I JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !!!!!!""""""""""""""##$%%%%%%%%%%%%%%%&&&&&&&&&&&&&&&&&&&&&&&&&&&&'''''''((((((((((((())))))))))))) ) ) ) ) )))))))))))******** +!+"+#+$+%+&+',(,),*,+,,,-,.,/,0,1,2,3-4.5.6.7.8.9.:.;/<0=1>1?1@1A1B1C1D1E2F2G2H2I2J2K2L2M2N3O3P3Q3R3S3T3U3V3W3X3Y3Z3[4\4]4^4_4`4a4b4c4d4e5f5g5h5i5j5k5l5m6n7o7p7q7r7s7t7u7v7w7x7y8z9{9|9}9~99999None)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, m is too light-weight for sparking to be productive, therefore it is more likely to be the parallelised deep  evaluation# of list-elements which saves time.Sums a list of rational type numbers.CAVEAT: though faster than V, 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.1CAVEAT: memory-use is proportional to chunk-size.Safe6Characters used to represent the digits of numbers in (-36 <= base <= 36)."Constant random-access lookup for .Constant reverse-lookup for ._Convert the specified integral quantity, to an alternative base, and represent the result as a .:Both negative integers and negative bases are permissible.The conversion to  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 A-representation of a number in the specified base, to an integer.9Both negative numbers and negative bases are permissible. *http://mathworld.wolfram.com/DigitSum.html. 'https://en.wikipedia.org/wiki/Digit_sum. *https://en.wikipedia.org/wiki/Digital_root.Safe"Defines the methods expected of a  prime-number generator. (Returns the constant list, defining the  Primorial. 'https://en.wikipedia.org/wiki/Primorial. +http://mathworld.wolfram.com/Primorial.html. .Returns the constant ordered infinite list of Mersenne numbers.^Only the subset composed from a prime exponent is returned; which is a strict superset of the Mersenne Primes. ,https://en.wikipedia.org/wiki/Mersenne_prime. 0http://mathworld.wolfram.com/MersenneNumber.html    Safe 0A number of decimal digits; presumably positive. The rate of convergence;  1https://en.wikipedia.org/wiki/Rate_of_convergence. The order of convergence;  1https://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 predicted number of terms which must be extracted from a series, if it is to converge to the required accuracy, at the specified linear convergence-rate.The convergence-rate< of a series, is the error in the series after summation of (n+1)th) terms, divided by the error after only n9 terms, as the latter tends to infinity. As such, for a  convergent] series (in which the error get smaller with successive terms), it's value lies in the range 0 .. 1. 1https://en.wikipedia.org/wiki/Rate_of_convergence.5Rounds the specified number, to a positive number of  .7Promotes the specified number, by a positive number of  . Reduces a : to the minimal form required for the specified number of  fractionalH decimal places; irrespective of the number of integral decimal places.A  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. &The precision of the initial estimate.The required precision.0The additional number of correct decimal digits.AThe number of places after the decimal point, which are required.   SafeMainly 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.AThe initial value doesn't need to be either positive or integral.Just for convenience.JRaise an arbitrary number to the specified positive integral power, using modular arithmetic.2Implements exponentiation as a sequence of either squares" or multiplications by the base;  8https://en.wikipedia.org/wiki/Exponentiation_by_squaring. 4https://en.wikipedia.org/wiki/Modular_exponentiation. Lower bound. [(n, n^2)] .Base.Modulus.Result.Safe>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. %https://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. 7https://en.wikipedia.org/wiki/Fermat%27s_little_theorem. 3https://en.wikipedia.org/wiki/Fermat_primality_test. 0https://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. /https://en.wikipedia.org/wiki/Carmichael_number. 2http://mathworld.wolfram.com/CarmichaelNumber.html.!An ordered list of the  Carmichael numbers;  /https://en.wikipedia.org/wiki/Carmichael_number. ! !!  !Safe "eThe interface required to iterate, from an estimate of the required value, to the next approximation.%"Defines the methods expected of a  square-root algorithm.(Contains an estimate for the  square-root of a value, and its accuracy.)<The result-type; actually, only the concrete return-type of +, stops it being a polymorphic instance of . Generalise  to operate on any  operand.*Uses L-precision floating-point arithmetic, to obtain an initial estimate for the  square-root, and its accuracy.+"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.0CAVEAT: the magnitude is twice the error in the  square-root.,'True if the specified estimate for the  square-root , is precise.-)For a given value and an estimate of its  square-root6, returns the number of decimals digits to which the  square-root, is accurate; including the integral digits.?CAVEAT: the result returned for an exact match has been bodged. "#$%&'()*+,- "#$%&'()*+,- %&'"#$)(-+*, "#$%&'()*+,-None.#Categorises the various algorithms./Algorithms based on the Arithmetic-geometric Mean.0 Lhttps://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula.1 3https://en.wikipedia.org/wiki/Borwein%27s_algorithm.2 &http://www.pi314.net/eng/ramanujan.php.3$Algorithms from which the digits of Pi slowly drip, one by one.4"Defines the methods expected of a Pi -algorithm./Most of the implementations naturally return a 0, but the spigot-algorithms naturally produce a [Int]; though representing PiF 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. ./0123456789 ./30124567 4567./0123./0123456789 None=Returns  (Just . sqrt) if the specified integer is a  square number (AKA perfect square). +https://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 squarer. 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. +https://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.A specialisation of >.=>=>=>=> Safe? 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@lDefines a series composed from a sum of terms, each one of which is the product of a coefficient and a base.9The coefficents and bases of the series are described in  Horner form; .Pi = c1 + (b1 * (c2 + b2 * (c3 + b3 * (...)))).E^The width of the spigot-table, required to accurately generate the requested number of digits.F Combines C and D<, and as a side-effect, expresses the ratio in lowest terms.@ABCDEF@ABCDEF@ABCDEF@ABCDEF Safe(Coerce the polymorphic type returned by  to our specific requirements.Coerce the polymorphic type % to suit the base used in our series..The type in which all arithmetic is performed.>A small dynamic range, 32 bits or more, is typically adequate.G: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.gDivide 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 h, from right to left, over the columns of a row in the spigot-table, continuously checking for overflow.mRelease any previously withheld result-digits, after any adjustment for overflow in the current result-digit.kWithhold the current result-digit until the risk of overflow in subsequent result-digits has been assessed.Call ..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 .HInitialises a spigot-table with the row of B.]Ensures that the row has suffient terms to accurately generate the required number of digits.?Extracts only those digits which are guaranteed to be accurate.%CAVEAT: the result is returned as an !, i.e. without any decimal point. G Data-row.HGHGH GH SafeI$Defines a series which converges to Pi.IIIISafeJ$Defines a series which converges to Pi.JJJJNoneK Define those Spigot(-algorithms which have been implemented.LA continued fraction discovered by Gosper.MA continued fraction discovered by  Rabinowitz and Wagon.KLMNOKLMKLMKLMNOSafeS-Defines a series corresponding to a specific  Ramanujan -formula.UGThe sequence of terms, the sum to infinity of which defines the series.VTThe ratio by which the sum to infinity of the sequence, must be scaled to result in Pi.W!The expected number of digits of Pi, per term in the series.STUVWSTUWVSTUVWSTUVWNoneXReturns Pi5, accurate to the specified number of decimal digits.XThis PiC-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.XXXSafeY-Defines a series corresponding to a specific Borwein -formula.\!The expected number of digits of Pi, per term in the series.YZ[\YZ[\YZ[\YZ[\None]Returns Pi5, accurate to the specified number of decimal digits.]This PiC-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^-Defines a series corresponding to a specific BBP -formula.`GThe constant numerators from which each term in the series is composed.aYGenerates the term-dependent denominators from which each term in the series is composed.bRThe ratio by which the sum to infinity of the series, must be scaled to result in Pi.c:The geometric ratio, by which successive terms are scaled.^_`abc^_c`ab^_`abc^_`abcNonedReturns Pi5, accurate to the specified number of decimal digits.dThis PiC-algorithm is parameterised by the type of other algorithms to use.&The number of decimal digits required.dddSafee/Defines the parameters of this specific series.eeeeSafef/Defines the parameters of this specific series.ffffNonegDefines those BBP)-type series which have been implemented.hA base-2^16 version of the formula.iA  nega-base 2^10 version of the formula.ghijkghighighijkSafeo%Merely to enhance self-documentation.CAVEAT: whilst p and o# can be independent types for both t and u, they interact for other hyper-exponents.p%Merely to enhance self-documentation."CAVEAT: whilst it may appear that p could be non-, the recursive definition for hyper-exponents above u, prevents this.x Returns the  power-tower of the specified base;  ,http://mathworld.wolfram.com/PowerTower.html.A synonym for  tetration;  'https://en.wikipedia.org/wiki/Tetration,  2http://www.tetration.org/Fractals/Atlas/index.html.yThe hyperoperation -sequence;  ,https://en.wikipedia.org/wiki/Hyperoperation.zThe Ackermann-Peter -function;  Bhttps://en.wikipedia.org/wiki/Ackermann_function#Ackermann_numbers.{True if !hyperoperation base hyperExponent' has the same value for each specified rank. opqrstuvwxyz{ opqrstuvwxyz{ poqrstuvwyzx{ opqrstuvwxyz{Safe|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~"Defines the methods expected of a  factorial -algorithm.~~~~None5The list-length beneath which to terminate bisection.9The ratio of the original list-length at which to bisect.CAVEAT: the value can overflow.4Reduces a list to a single scalar encapsulated in a  , using a divide-and-conquerE strategy, bisecting the list and recursively evaluating each part;  :https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.By choosing a bisectionRatio other than (1 % 2), the bisection can be made asymmetrical. The specified ratio represents the length of the left-hand portion, over the original list-length; eg. (1 % 3): results in the first part, half the length of the second.oThis 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  Ahttps://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29l, in which the list is exploded into a binary tree-structure (each leaf of which contains a list of up to  minLength integers, and each node of which contains an associative binary operator), and then collapsed to a scalar, by application of the operators.)Multiplies the specified list of numbers.Since the result can be large,  is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms.#Sums the specified list of numbers.Since the result can be large,  is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms. Multiplication is required for the addition of \ numbers by cross-multiplication; this function is unlikely to be useful for other numbers.9The ratio of the original list-length at which to bisect._For 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.9The ratio of the original list-length at which to bisect._For 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.9The ratio of the original list-length at which to bisect._For 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.NoneEncapsulates both  arithmetic and  geometric means.The type of the geometric mean;  ,https://en.wikipedia.org/wiki/Geometric_mean.The type of the arithmetic mean;  -https://en.wikipedia.org/wiki/Arithmetic_mean. Accessor. Accessor.0Returns an infinite list which converges on the Arithmetic-geometric mean.$Returns the bounds within which the  has been constrained.Checks that both means# are positive, as required for the geometric mean to be consistently real.NoneReturns Pi5, accurate to the specified number of decimal digits.This algorithm is based on the arithmetic-geometric mean of 1 and  (1 / sqrt 2)], but there are many confusingly similar formulations. The algorithm I've used here, where a is the arithmetic mean and g is the geometric mean-, is equivalent to other common formulations:  pi = (a[N-1] + g[N-1])^2 / (1 - sum [2^n * (a[n] - g[n])^2]) where n = [0 .. N-1] => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 - 2*a[n]*g[n] + g[n]^2)]) => 4*a[N]^2 / (1 - sum [2^n * (a[n]^2 + 2*a[n]*g[n] + g[n]^2 - 4*a[n]*g[n])]) => 4*a[N]^2 / (1 - sum [2^n * ((a[n] + g[n])^2 - 4*a[n]*g[n])]) => 4*a[N]^2 / (1 - sum [2^(n-1) * 4 * (a[n-1]^2 - g[n-1]^2)]) where n = [1 .. N] => 4*a[N]^2 / (1 - sum [2^(n+1) * (a[n-1]^2 - g[n-1]^2)])None!Defines the available algorithms. None Does for , what  does for type %, in that it makes it an instance of  under addition.Access the polymorphic payload. Does for , what  does for type %, in that it makes it an instance of  under multiplication.Access the polymorphic payload.<Define both the operations applicable to all members of the ring, and its mandatory members.Minimal definition; , , , , .Raise a ring1-member to the specified positive integral power.]Exponentiation is implemented as a sequence of either squares of, or multiplications by, the ring -member;  8https://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. 6768!NoneDefines 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. Numerator. Denominator. Numerator. Denominator.LHS.RHS.Modulus. Numerator. Denominator."Safe!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.Defines a container for the .FAn 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.JOn being rolled, the trace of the spokes, identifies candidates which are coprime to those primes from which the wheel was composed.OOne can alternatively view this as a set of vertical nested rings, each with a prime circumferenceC, 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.CCAVEAT: 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)]BThe number of spokes also grows rapidly with the number of primes:  zip [0 ..] . scanl (*) 1 . map pred $ [2,3,5,7,11,13,17,19,23,29,31] [(0,1),(1,1),(2,2),(3,8),(4,48),(5,480),(6,5760),(7,92160),(8,1658880),(9,36495360),(10,1021870080),(11,30656102400)]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 .Uses a Sieve of Eratosthenes ( 3https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes-), to generate an initial sequence of primes.JAlso generates an infinite sequence of candidate primes, each of which is coprime" to the primes just found, e.g.: filter ((== 1) . (gcd (2 * 3 * 5 * 7))) [11 ..] = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121 ..]; NB 121 isn't prime.$CAVEAT: the use, for efficiency, of  Data.IntMapP, limits the maximum bound of this sequence, though not to a significant extent.9The optimal number of low primes from which to build the wheel1, grows with the number of primes required; the  circumference should be approximately the  square-root8 of the number of integers it will be required to sieve.JCAVEAT: one greater than this is returned, which empirically seems better.Smart constructor for a wheel) from the specified number of low primes.9The optimal number of low primes from which to build the wheel1, grows with the number of primes required; the  circumference should be approximately the  square-root8 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 on1 the axis, that aren't part of this symmetry. Eg: { nPrimes Gaps ====== ==== 0 [1] 1 [2] -- The terminal gap for all subsequent wheels is '2'; [(succ circumference `mod` circumference) - (pred circumference `mod` circumference)]. 2 [4,2] -- Both points are on the axis, so the symmetry isn't yet clear. 3 [6,4,2,4,2,4,6,2] 4 [10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2]ZExploitation of this property has proved counter-productive, probably because it requires strict evaluationB, exposing the user to the full cost of inadvertently choosing a wheel/, 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 squareG, 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 ..]!The number to square and multiplyA  rolling wheel0, the track of which, delimits the gaps between coprime candidates. #NoneDefines the types of  quadraticC, available to test the potential primality of a candidate integer./Suitable for primality-testing numbers meeting (n  4 == 1)./Suitable for primality-testing numbers meeting (n  6 == 1)./Suitable for primality-testing numbers meeting (n  12 == 11).UThere's no polynomial which can assess primality, because the candidate is composite.TThe constant modulus used to select the appropriate quadratic for a prime candidate.FThe constant list of primes factored-out by the unoptimised algorithm.HThe constant number of primes factored-out by the unoptimised algorithm.ETypically the set of primes which have been built into the specified wheel, but never fewer than .+The period over which the data returned by  repeats.$Defines which, if any, of the three  quadratics: is appropriate for the primality-test for each candidate.Since this algorithm uses modular arithmetic, the range! of results repeat after a short domain related to the modulus. Thus one need calculate at most one period of this cycle, but fewer if the maximum prime required falls within the first cycle of results.Because the results are bounded%, they're returned in a zero-indexed arrays, to provide efficient random access; the first few elements should never be required, but it makes query clearer. ,https://en.wikipedia.org/wiki/Sieve_of_Atkin.#The constant, infinite list of the squares, of integers increasing from 1. Returns the ordered list of those values with an odd( number of occurrences in the specified  unordered list.CAVEAT: this is expensive in both execution-time and space. The typical imperative-style implementation accumulates polynomial-solutions in a  mutable arrayM indexed by the candidate integer. This doesn't translate seamlessly to the pure functional domain where arrays naturally immutable, so we sort a list{ of polynomial-solutions, then measure the length of the solution-spans, corresponding to viable candidates. Regrettably,  (implemented in GHC by  mergesort) has a time-complexity  O(n*log n)( which is greater than the theoretical O(n) of the whole Sieve of Atkin; GHC's old qsort!-implementation is even slower :(DReturns the ordered list of solutions aggregated from each of three bivariate quadratics;  z = f(x, y).YFor a candidate integer to be prime, it is necessary but insufficient, that there are an odd number of solutions of value  candidate.`At most one of these three polynomials is suitable for the validation of any specific candidate z, depending on lookupPolynomialTypeJ. so the three sets of solutions are mutually exclusive. One coordinate (x, y)?, can have solutions in more than one of the three polynomials.1This algorithm exhaustively traverses the domain (x, y), for resulting z of the required modulus. Whilst it tightly constrains the bounds of the search-space, it searches the domain methodically rather than intelligently.Generates the bounded list of multiples, of the square> of the specified prime, skipping those which aren't required.Generates the constant bounded list of  prime-numbers. /http://cr.yp.to/papers/primesieves-19990826.pdfA specialisation of ?, which reduces both the execution-time and the space required.The maximum prime required."The maximum prime-number required.@Used to generate the gaps between prime multiples of the square.The prime.The maximum bound.@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. $None A specialisation of .A specialisation of . Combine a queue , with a map/, to form a repository to hold prime-multiples.!A map of the multiples of primes.,An ordered queue of the multiples of primes.The  counterpart to <=.The  counterpart to <>.CAVEAT: because  Data.List.tail []  returns an error, whereas  tail' Data.Sequence.empty  returns *, this function is for internal use only.A refinement of the Sieve Of Eratosthenes4, which pre-sieves candidates, selecting only those coprime6 to the specified short sequence of low prime-numbers.:The short sequence of initial primes are represented by a ', of parameterised, but static, size;  1https://en.wikipedia.org/wiki/Wheel_factorization.YThe 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 squareq of the prime from which it was generated, the vast majority will be larger than the maximum prime ultimately demanded, and the effort of constructing and storing this list, is consequently wasted. Many implementations solve this, by requiring specification of the maximum prime required, thus allowing the construction of redundant lists of multiples to be avoided.NThis implementation doesn't impose that constraint, leaving a requirement for rapid! storage, which is supported by  appending the list of prime-multiples, to a queue?. If a large enough candidate is ever generated, to match the head of the list of prime-multiples, at the head of this queue, then the whole list( of prime-multiples is dropped from the queue , but the tail of this listq 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 T is used for these subsequent multiples. This solution is faster than just using a Data.PQueue.Min.CAVEAT: has linear O(n) space-complexity.A specialisation of , which approximately doubles* the speed and reduces the space required.'CAVEAT: because the algorithm involves squaresP of primes, this implementation will overflow when finding primes greater than 2^16 on a 32-bit machine.  %Safe"The type of an arbitrary monomial.CAVEAT: though a monomialM has an integral power, this contraint is only imposed at the function-level. Accessor. Accessor. if the exponent is both integral and non-negative.5CAVEAT: 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.4477&NoneThe type of an arbitrary  univariateL polynomial; actually it's more general, since it permits negative powers ( 0https://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 9, this is implemented at the function-level, as required.#The structure permits gaps between  exponents , in which  coefficientsW are inferred to be zero, thus enabling efficient representation of sparse polynomials. CAVEAT: the  is required to; be ordered by  descending exponent (ie. reverse  ,https://en.wikipedia.org/wiki/Monomial_order9); 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 ?@, but  isn't an instance of ?A& since we may want to operate on both type-parameters.%CAVEAT: the caller is required to re-T the resulting polynomial depending on the nature of the transformation of the data.7Returns 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.+Smart constructor. Constructs an arbitrary  polynomial. Constructs a  polynomial with zero terms.Constructs a constant monomial, independent of the  indeterminate. True if all  exponents6 are in the order defined by the specified comparator. 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.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. >https://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. 4https://en.wikipedia.org/wiki/Degree_of_a_polynomial. 2http://mathworld.wolfram.com/PolynomialDegree.html.Scale-up the specified  polynomial by a constant monomial factor. 3https://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)  mI, this will result in arithmetic operatons on unnecessarily big integers.#Reduces all the coefficients using modular arithmetic. Evaluate the  polynomial at a specific  indeterminate.ACAVEAT: requires positive exponents; but it wouldn't really be a  polynomial otherwise.If the  polynomial4 is very sparse, this may be inefficient, since it memoizes8 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;  -https://en.wikipedia.org/wiki/Polynomial_ring.  Gradient. Constant.LHS.RHS.Modulus. The base.0The exponent to which the base should be raised. The modulus. The result.Modulus.The  indeterminate. The Result.7'None A type of , in which the  leading term is required to have a  coefficient of one.+Smart constructor. Constructs an arbitrary monic polynomial.(None<Defines a closed (inclusive) interval of consecutive values. Accessor. Accessor.Construct the unsigned closed unit-interval;  +https://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./The distance between the endpoints, which for o quantities is the same as the number of items in closed interval; though the latter concept would return type .CAVEAT: the implementation accounts for the potential fence-post error, for closed intervals of integers, but this results in the opposite error when used with  Fractional< quantities. So, though most of the module merely requires ), this function is further restricted to . Converts % to a list by enumerating the values.(CAVEAT: produces rather odd results for R types, but no stranger than considering such types Enumerable in the first place.Reduces . to a single integral value encapsulated in a  , using a divide-and-conquer strategy, bisecting the interval' and recursively evaluating each part;  :https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.By choosing a ratio other than (1 % 2), the bisection can be made asymmetrical. The specified ratio represents the length of the left-hand portion over the original list-length; eg. (1 % 3): results in the first part, half the length of the second.jThis 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  Ahttps://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29 , in which X is exploded into a binary tree-structure (each leaf of which contains a list of up to  minLength integers, and each node of which contains an associative binary operator), and then collapsed to a scalar, by application of the operators.7Multiplies the consecutive sequence of integers within .Since the result can be large, { is used to form operands of a similar order of magnitude, thus improving the efficiency of the big-number multiplication.#The magnitude of the require shift.The interval to be shifted.The monoid's constructor.7The ratio of the original span, at which to bisect the .For efficiency, the intervalG will not be bisected, when it's length has been reduced to this value.The resulting scalar.!The ratio at which to bisect the .For efficiency, the intervalG will not be bisected, when it's length has been reduced to this value.The resulting product. )None9Defines a common interface for probability-distributions. Describes "discrete probability-distributions;  Vhttps://en.wikipedia.org/wiki/List_of_probability_distributions#Discrete_distributions. Defines an Poisson -distribution with a particular lambda;  2https://en.wikipedia.org/wiki/Poisson_distribution. Defines an  Geometric8-distribution with a particular probability of success;  4https://en.wikipedia.org/wiki/Geometric_distribution. Describes $continuous probability-distributions;  Xhttps://en.wikipedia.org/wiki/List_of_probability_distributions#Continuous_distributions. Defines an  Exponential -distribution with a particular lambda;  6https://en.wikipedia.org/wiki/Exponential_distribution.QDefines a distribution whose logarithm is normally distributed with a particular mean & variance;  'https://en.wikipedia.org/wiki/Lognormal. Defines a Normal -distribution with a particular mean & variance;  1https://en.wikipedia.org/wiki/Normal_distribution. Defines a Uniform-distribution within a closed interval;  2https://en.wikipedia.org/wiki/Uniform_distribution. DThe maximum integer which can be accurately represented as a Double.nDetermines the minimum positive floating-point number, which can be represented by using the parameter's type.:Only the type of the parameter is relevant, not its value. 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. :https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform. YUses the supplied random-number generator, to generate a conceptually infinite list, of normally distributed# random numbers, with standardized mean=0, and variance=1. 1https://en.wikipedia.org/wiki/Normal_distribution,  4http://mathworld.wolfram.com/NormalDistribution.html.Stretches and shifts a  distribution to achieve the required mean and standard-deviation. Uses the supplied random-number generator, to generate a conceptually infinite population, with the specified continuous probability-distribution.Uses the supplied random-number generator, to generate a conceptually infinite population, of random integers conforming to the Poisson distribution;  2https://en.wikipedia.org/wiki/Poisson_distribution.5CAVEAT: 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 . Uses the supplied random-number generator, to generate a conceptually infinite 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.  A generator of uniformly distributed random numbers./Defines the required approximate value of both mean and variance. A generator of uniformly distributed random numbers.               *Safe Describes an  exponential, in terms of its base and exponent. Accessor. Accessor. Construct an  merely raised to the 1st power.@The value of the resulting exponential is the same as specified base;  .https://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.3The power to which the exponential is to be raised. The result.48+None  )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 exponentP 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.RCAVEAT: this is tolerably efficient for sporadic insertion; to insert a list, use #.#4Multiplies 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.$2Divides 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.XCAVEAT: 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 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. !"#$%& "&!#$%  !"#$%&#7$7%8,None'The algorithms by which  factorial has been implemented.(The integers from which the  factorial# is composed, are multiplied using Data.Interval.product'.)The  prime factors of the  factorialL are extracted, then raised to the appropriate power, before multiplication.* Returns the  prime factors , of the  factorial of the specifed integer.EPrecisely all the primes less than or equal to the specified integer n, are included in n!T; only the multiplicity of each of these known prime components need be determined. 5https://en.wikipedia.org/wiki/Factorial#Number_theory.CAVEAT: currently a hotspot.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.+ 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.HIt 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).A prime number.:The integer, the factorial of which the prime is a factor.6The number of times the prime occurs in the factorial.+@The lower bound of the integer-range, whose product is returned.*The number of integers in the range above. The result.,@The 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../')(*+,-'()*+,-'()*+,-./-7-None3Defines the parameters of the Borwein series.3333.None4 Define those Borwein$-series which have been implemented.TThough currently there's only one, provision has been made for the addition of more.5 3https://en.wikipedia.org/wiki/Borwein%27s_algorithm.456745454567/None;Defines the parameters of the  Chudnovsky series.;;;;0None<Defines the parameters of the  Ramanujan series.<<<<1None= Define those  Ramanujan$-series which have been implemented.>The original version.?A variant found by the Chudnovsky brothers.=>?@A=?>=>?=>?@A2None EDetermines the mean of the specified numbers;  "https://en.wikipedia.org/wiki/Mean.,Should the caller define the result-type as ,, then it will be free from rounding-errors.FDetermines the root mean square of the specified numbers;  .https://en.wikipedia.org/wiki/Root_mean_square.GDetermines the  weighted mean of the specified numbers;  6https://en.wikipedia.org/wiki/Weighted_arithmetic_mean.NThe specified value is only evaluated if the corresponding weight is non-zero.,Should the caller define the result-type as ,, then it will be free from rounding-errors.pCAVEAT: because the operand is more general than a list, no optimisation is performed when supplied a singleton. Measures the  dispersion of a  population of results from the mean value;  4https://en.wikipedia.org/wiki/Statistical_dispersion.,Should the caller define the result-type as ,, then it will be free from rounding-errors.HDetermines the exact variance of the specified numbers;  &https://en.wikipedia.org/wiki/Variance.,Should the caller define the result-type as ,, then it will be free from rounding-errors.IDetermines the standard-deviation of the specified numbers;  0https://en.wikipedia.org/wiki/Standard_deviation.JDetermines the average absolute deviation of the specified numbers;  Khttps://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.KDetermines the coefficient-of-variance of the specified numbers;  6https://en.wikipedia.org/wiki/Coefficient_of_variation.LThe number of unordered  combinations of r objects taken from n;  )https://en.wikipedia.org/wiki/Combination.MThe number of  permutations of r objects taken from n;  *https://en.wikipedia.org/wiki/Permutations. EFG9Each pair consists of a value & the corresponding weight.HIJKL/The total number of items from which to select. The number of items in a sample.The number of combinations.M/The total number of items from which to select. The number of items in a sample.The number of permutations. EFGHIJKLM EFGHIJKLM EFGHIJKLM3None %Returns an improved estimate for the  square-rootY of the specified value, to the required precision, using the supplied initial estimate..NThe algorithms by which the  square-root has been implemented.O Whttps://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Bakhshali_approximationP \https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Continued_fraction_expansion.Q /https://en.wikipedia.org/wiki/Halley%27s_method.R /https://en.wikipedia.org/wiki/Newton%27s_method.S Mhttps://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Taylor_series.T The number of terms in a series.Uses continued-fractions#, to iterate towards the principal  square-root% of the specified positive integer;  Rhttps://en.wikipedia.org/wiki/Solving_quadratic_equations_with_continued_fractions,  Vhttps://en.wikipedia.org/wiki/Generalized_continued_fraction#Roots_of_positive_numbers,  \https://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.pdfThe convergence  1https://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;  Mhttps://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. Mhttps://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.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; S Terms Convergence ===== =========== 2 terms /quadratic/ 3 terms /cubic//Iterates from the estimated value, towards the  square-root@, a sufficient number of times to achieve the required accuracy.The required precision. The value for which to find the  square-root.NOPQRST8The number of terms of the infinite series, to evaluate.The value for which the  square-root is required.An initial estimate.UVWNOPQRSTTNOPQRS NOPQRSTUVW4None ["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  2)0 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.N.B.: rather then using (primeFactor <= sqrt numerator)X to filter the candidate prime-factors of a given numerator, one can alternatively use (numerator >= primeFactor ^ 2)D to filter what can potentially be factored by a given prime-factor.OCAVEAT: suffers from rounding-errors, though no consequence has been witnessed.^>A constant, zero-indexed, conceptually infinite, list, of the smoothness of all positive integers. +https://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. ?https://en.wikipedia.org/wiki/Smooth_number#Powersmooth_numbers.`Filters ^!, to derive the constant list of Hamming-numbers. ,https://en.wikipedia.org/wiki/Regular_number.aEuler'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)lCAVEAT: checks neither the primality nor the bounds of the specified value; therefore for internal use only.bThe number of coprimes6 less than or equal to the specified positive integer. 8https://en.wikipedia.org/wiki/Euler%27s_totient_function. 1http://mathworld.wolfram.com/TotientFunction.html.AKA EulerPhi.c=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.d/A constant, conceptually infinite, list of the  square-free3 numbers, i.e. those which aren't divisible by any perfect square. 1https://en.wikipedia.org/wiki/Square-free_integer. [\]^_`abcd [\]^_`abcd [\]^_`abcd [\]^_`abcd5NoneeAThe algorithms by which prime-factorisation has been implemented. <https://en.wikipedia.org/wiki/Dixon%27s_factorization_method.f =https://en.wikipedia.org/wiki/Fermat%27s_factorization_method.g ,https://en.wikipedia.org/wiki/Trial_division. <https://en.wikipedia.org/wiki/Dixon%27s_factorization_method. =https://en.wikipedia.org/wiki/Fermat%27s_factorization_method. <http://mathworld.wolfram.com/FermatsFactorizationMethod.html. 3https://en.wikipedia.org/wiki/Congruence_of_squares. i = f1 * f2Y Assume a non-trivial factorisation, ie. one in which both factors exceed one. => +i = (larger + smaller) * (larger - smaller)9 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. => 2(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.4Decomposes the specified integer, into a product of prime-factors, using  ;http://mathworld.wolfram.com/DirectSearchFactorization.html, AKA  ,https://en.wikipedia.org/wiki/Trial_division.+This works best when the factors are small. efghiefgefgefghi6NoneUses Trial Divisiont, to determine whether the specified candidate is indivisible by all potential denominators from the specified list.m3For 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;  1https://en.wikipedia.org/wiki/Wheel_factorization.The numerator.4The denominators of which it must not be a multiple.mmmm7Nonen=The implemented methods by which the primes may be generated.oThe Sieve of Atkin, optimised using a @ of optimal size, for primes up to the specified maximum bound;  ,https://en.wikipedia.org/wiki/Sieve_of_Atkin.pThe Sieve of Eratosthenes ( 3https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), optimised using a .q3For each candidate, confirm indivisibility, by all primes smaller than its  square-root, optimised using a .r 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.s.nopqrstunqoprsnopqrsnopqrstu8NoneyThe 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. 2https://en.wikipedia.org/wiki/Multiplicative_order. 5http://mathworld.wolfram.com/MultiplicativeOrder.html.yBase.Modulus.Result.yyy9NonezThe algorithms by which  primality-testing has been implemented.{ 0https://en.wikipedia.org/wiki/AKS_primality_test.| Ahttps://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test.An implementation of the Agrawal-Kayal-Saxena primality-test;  0https://en.wikipedia.org/wiki/AKS_primality_test , using the Lenstra and  Pomerance algorithm.JCAVEAT: this deterministic algorithm has a theoretical time-complexity of O(log^6)J, and therefore can't 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  coefficientsu are stored, and is never substituted for a specific value. 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  compositec; regrettably the converse isn't true. Amongst the set of possible bases, over three-quarters are  witnesses to the compositeness of a  composite3 candidate, the remainder belong to the subset of liarsp. In consequence, many false results must be accumulated for different bases, to convincingly identify a prime.Repeatedly calls ;, to progressively increase the probability of detecting a  compositeG number, until ultimately the candidate integer is proven to be prime.QShould all bases be tested, then the test is deterministic, but at an efficiency lower% than performing prime-factorisation.qThe test becomes deterministic, for any candidate integer, when the number of tests reaches the limit defined by  Eric Bach.aA testing of smaller set of bases, is sufficient for candidates smaller than various thresholds;  )http://primes.utm.edu/prove/prove2_3.html. 9https://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.z{|Candidate integer.Base.}~z{|z{|z{|}~BCDEFGHIJKLMNOPQRSTUVWXYZ[\]I^_`abcdeIfghijklmnopqrsItuvwxyz{ | } ~   u tttIBot  Y B !!!!!!"""";""""""""""##$%%%%%%%%%Y%%%%%%&&&&&&&&&&&&&&&&&&&&&]&&&&&&&'''''''((((( ( ( ( ( (((())))))))))))))))) )!)")#)$)%)&)')()))*)+*,*-**.***/*0+1+2+3+4+5+6+,,7,8,9,:,;,<,,,,,-..=...../011>1?1111122@2A222B2C2D2E33F3G3H3I3J3K3L333334I494M4N4O4P4Q4R4S4T55U5V555556W77X7Y7V7Z7[777778\99]9^99999_`abcdefghijhik_lmno_phiqrst u v_w _x y z { | } ~   _f      """##_##############$$$$$$$$&&&&&&'(hi()))++0+,233333_55556999%factory-0.3.0.0-LIJG097jnwMmb3ceEvSqvFactory.Math.SummationFactory.Math.RadixFactory.Math.PrimesFactory.Math.PrecisionFactory.Math.PowerFactory.Math.PrimalityFactory.Math.SquareRootFactory.Math.PiFactory.Math.PerfectPower0Factory.Math.Implementations.Primes.TurnersSieve-Factory.Math.Implementations.Pi.Spigot.Series-Factory.Math.Implementations.Pi.Spigot.Spigot6Factory.Math.Implementations.Pi.Spigot.RabinowitzWagon-Factory.Math.Implementations.Pi.Spigot.Gosper0Factory.Math.Implementations.Pi.Spigot.Algorithm0Factory.Math.Implementations.Pi.Ramanujan.Series8Factory.Math.Implementations.Pi.Ramanujan.Implementation.Factory.Math.Implementations.Pi.Borwein.Series6Factory.Math.Implementations.Pi.Borwein.Implementation*Factory.Math.Implementations.Pi.BBP.Series2Factory.Math.Implementations.Pi.BBP.Implementation+Factory.Math.Implementations.Pi.BBP.Bellard-Factory.Math.Implementations.Pi.BBP.Base65536-Factory.Math.Implementations.Pi.BBP.AlgorithmFactory.Math.HyperoperationFactory.Math.FibonacciFactory.Math.FactorialFactory.Math.DivideAndConquer$Factory.Math.ArithmeticGeometricMean0Factory.Math.Implementations.Pi.AGM.BrentSalamin-Factory.Math.Implementations.Pi.AGM.AlgorithmFactory.Data.RingFactory.Data.QuotientRingFactory.Data.PrimeWheel0Factory.Math.Implementations.Primes.SieveOfAtkin7Factory.Math.Implementations.Primes.SieveOfEratosthenesFactory.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.Implementations.PrimeFactorisation1Factory.Math.Implementations.Primes.TrialDivision-Factory.Math.Implementations.Primes.Algorithm Factory.Math.MultiplicativeOrder&Factory.Math.Implementations.PrimalityData.PrimeWheel PrimeWheel Data.Listheadtail Data.FunctorfmapFunctorsum'sumR'sumRtoBasefromBasedigitSum digitalRoot Algorithmicprimes primorialmersenneNumbers DecimalDigitsConvergenceRateConvergenceOrderlinearConvergencequadraticConvergencecubicConvergencequarticConvergencegetIterationsRequiredgetTermsRequiredroundTopromotesimplifysquarecube squaresFromcubeRoot raiseModuloisPrime areCoprimeisFermatWitnessisCarmichaelNumbercarmichaelNumbersIteratorstepconvergenceOrdersquareRootFrom squareRootEstimateResult getEstimategetDiscrepancy isPrecise getAccuracyCategoryAGMBBPBorwein RamanujanSpigotopenRopenIopenS$fAlgorithmicCategory$fDefaultCategory $fEqCategory$fReadCategory$fShowCategorymaybeSquareNumberisPerfectPower turnersSieveSeriesMkSeries coefficientsbaseNumeratorsbaseDenominatorsnTermsbasesdecimalseries AlgorithmGosperRabinowitzWagon$fAlgorithmicAlgorithm$fDefaultAlgorithm $fEqAlgorithm$fReadAlgorithm$fShowAlgorithmtermsgetSeriesScalingFactorconvergenceRate numeratorsgetDenominatorsseriesScalingFactorbase Base65536Bellard HyperExponentBase successionadditionmultiplicationexponentiation tetration pentationhexation powerTowerhyperoperationackermannPeterareCoincidental fibonacciprimeIndexedFibonacci factorial MinLengthBisectionRatiodivideAndConquerproduct' GeometricMeanArithmeticMeangetArithmeticMeangetGeometricMean convergeToAGMspreadisValid BrentSalaminRing=+==*=additiveInversemultiplicativeIdentityadditiveIdentity=-==^ $fMonoidSum$fMonoidProduct $fReadProduct $fShowProduct $fReadSum $fShowSum QuotientRingquotRem'quot'rem'areCongruentModulo isDivisibleByDistanceNPrimesPrimeMultiplesgetPrimeComponents getSpokeGapsgetCircumference getSpokeCountestimateOptimalSize mkPrimeWheelrotaterollgenerateMultiples$fShowPrimeWheel sieveOfAtkin$fEqPolynomialTypesieveOfEratosthenesMonomialgetCoefficient getExponent isMonomial<=>=~<*>doubleshiftCoefficient shiftExponentnegateCoefficientmod'realCoefficientToFrac PolynomialliftgetLeadingTerm normalise mkConstantmkLinear mkPolynomialzerooneinAscendingOrderinDescendingOrder isNormalisedisMonicisZero isPolynomial getDegree*=evaluaterealCoefficientsToFrac$fQuotientRingPolynomial$fRingPolynomial$fEqPolynomial$fShowPolynomialMonicPolynomial getPolynomialmkMonicPolynomial$fQuotientRingMonicPolynomial$fRingMonicPolynomial$fEqMonicPolynomial$fShowMonicPolynomialInterval getMinBound getMaxBoundclosedUnitInterval mkBounded preciselyshiftelem' isReversedsplitAt'toList DistributiongeneratePopulationgetMeangetStandardDeviation getVarianceDiscreteDistributionPoissonDistributionShiftedGeometricDistributionContinuousDistributionExponentialDistributionLogNormalDistributionNormalDistributionUniformDistributionmaxPreciseIntegerboxMullerTransform&generateStandardizedNormalDistributiongenerateContinuousPopulationgenerateDiscretePopulation"$fDistributionDiscreteDistribution$$fDistributionContinuousDistribution#$fSelfValidatorDiscreteDistribution%$fSelfValidatorContinuousDistribution$fEqContinuousDistribution$fReadContinuousDistribution$fShowContinuousDistribution$fEqDiscreteDistribution$fReadDiscreteDistribution$fShowDiscreteDistribution ExponentialgetBase rightIdentity<^invertFactorsreduceinsert'>*<>/<>^ BisectionPrimeFactorisation primeFactorsrisingFactorialfallingFactorial!/! Borwein1993Classic ChudnovskygetRootMeanSquaregetWeightedMeangetAverageAbsoluteDeviationgetCoefficientOfVariancenCrnPrBakhshaliApproximationContinuedFraction HalleysMethodNewtonRaphsonIteration TaylorSeriesTerms$fIteratorAlgorithmmaxBoundPrimeFactor smoothnesspowerSmoothnessregularNumbersprimePowerTotient eulersTotientomega squareFree FermatsMethod TrialDivision trialDivision SieveOfAtkinSieveOfEratosthenes TurnersSieve WheelSievemultiplicativeOrderAKS MillerRabinGHC.RealRational Data.FoldablesumdigitsencodesdecodesGHC.BaseStringghc-prim GHC.TypesCharTrue FractionalrSqrt GHC.FloatsqrtRealDouble integer-gmpGHC.Integer.TypeIntegerisPerfectPowerIntQuotRemquotRemRatioIcarryAndDivideprocessColumnsmkRow CoefficientsPi PreDigits getQuotient getRemainderIntegralMonoidSum Data.MonoidGHC.NumNumgetSumProduct getProductMkSum MkProduct Repository findCoprimes MkPrimeWheelPolynomialTypeModFourmodModSix ModTwelveNone atkinsModulusinherentPrimesnInherentPrimesgetPrefactoredPrimespolynomialTypeLookupPeriodpolynomialTypeLookupsquaresfilterOddRepetitions Data.OldListsortfindPolynomialSolutionsgenerateMultiplesOfSquareTosieveOfAtkinInt RepositoryIntPrimeMultiplesMapIntPrimeMultiplesMapPrimeMultiplesQueuehead'containers-0.5.7.1 Data.SequenceSeqtail'empty Data.Map.BaseMapsieveOfEratosthenesInt MonomialListgetMonomialListpruneCoefficientsinOrder isReduced MkPolynomialMkMonicPolynomial getLengthIntGHC.EnumEnumminPositiveFloat reProfilegeneratePoissonDistribution reduceSorted sumExponentsprimeMultiplicitygetDispersionFromMeanProblemSpecificationsquareRootByContinuedFractiontaylorSeriesCoefficientssquareRootByTaylorSeriessquareRootByIterationdiv DixonsMethodfactoriseByDixonsMethodfactoriseByFermatsMethodfactoriseByTrialDivisionisIndivisibleBy%primes-0.2.1.0-BN5qcmPxb1H2keY7Pz9jFXData.Numbers.Primes wheelSieve isPrimeByAKSwitnessesCompositenessisPrimeByMillerRabin