IGLib
1.7.2
The IGLib base library EXTENDED - with other lilbraries and applications.
|
Contains methods that compute advanced functions of integer arguments. More...
Static Public Member Functions | |
static double | Factorial (int n) |
Computes the factorial of an integer. More... | |
static double | LogFactorial (int n) |
Computes the logrithm of the factorial of an integer. More... | |
static double | BinomialCoefficient (int n, int m) |
Computes a binomial coefficient. More... | |
static IEnumerable< double > | BinomialCoefficients (int n) |
Enumerates the binomial coefficients of a given order. More... | |
static double | DoubleFactorial (int n) |
Computes the double factorial of the given integer. More... | |
static double | LogDoubleFactorial (int n) |
Computes the natural logarithm of the double factorial of the given number. More... | |
static double | HarmonicNumber (int n) |
Computes the given harmonic number. More... | |
static double | FibonacciNumber (int n) |
Computes a Fibonacci number. More... | |
static double | BernoulliNumber (int n) |
Computes the given Bernoulli number. More... | |
static double | BellNumber (int n) |
Computes the given Bell number. More... | |
static long | GCF (long u, long v) |
Computes the greatest common factor of two integers. More... | |
static long | LCM (long u, long v) |
Computes the least common multiple of two integers. More... | |
static int | PowMod (int b, int e, int m) |
Computes a power of an integer in modular arithmetic. More... | |
static IEnumerable< int[]> | Partitions (int n) |
Enumerates all partitions of the given integer More... | |
static bool | IsPrime (int n) |
Determines whether the given integer is prime. More... | |
Static Private Member Functions | |
static long[] | CreateFactorialTable (int n) |
static long | DoubleFactorial_Multiply (int n) |
static double | LogDoubleFactorial_Gamma (int n) |
static bool | IsProbablyPrime (int n, int m, int s, int d, int w) |
static void | FactorByTrialDivision (List< Factor > factors, ref int n) |
static void | FactorByPollardsRhoMethod (List< Factor > factors, ref int n) |
Static Private Attributes | |
static readonly long[] | factorialTable = CreateFactorialTable(20) |
static readonly double | LogLongMax = Math.Log(Int64.MaxValue) |
Contains methods that compute advanced functions of integer arguments.
|
inlinestaticprivate |
|
inlinestatic |
Computes the factorial of an integer.
n | The argument, which must be non-negative. |
The factorial of an integer n is the product of all integers from 1 to n. For example, 4! = 4 * 3 * 2 * 1 = 24.
n! also has a combinatorial intrepretation as the number of permutations of n objects. For example, a set of 3 objects (abc) has 3! = 6 permutations: (abc), (bac), (cba), (acb), (cab), (bca).
Because n! grows extremely quickly with increasing n, we return the result as a double, even though the value is always an integer. (13! would overlow an int, 21! would overflow a long, 171! overflows even a double.)
In order to deal with factorials of larger numbers, you can use the LogFactorial method, which returns accurate values of ln(n!) even for values of n for which n! would overflow a double.
The factorial is generalized to non-integer arguments by the Γ function (AdvancedMath.Gamma(double)).
ArgumentOutOfRangeException | n is negative. |
References Meta.Numerics.Functions.AdvancedMath.Gamma().
Referenced by Test.OrthogonalPolynomialsTest.AssociatedLaguerreOrthonormality(), Meta.Numerics.Functions.AdvancedMath.BesselJ_Series(), Test.AdvancedMathTest.BesselModifiedBesselRelationship(), FutureTest.FutureTest.BesselY(), FutureTest.FutureTest.BesselY_Series(), FutureTest.FutureTest.BesselY_Series2(), Meta.Numerics.Statistics.Distributions.ExponentialDistribution.Cumulant(), Meta.Numerics.Statistics.Distributions.ChiSquaredDistribution.Cumulant(), Meta.Numerics.Statistics.Distributions.LogisticDistribution.Cumulant(), Meta.Numerics.Statistics.Distributions.GammaDistribution.Cumulant(), Meta.Numerics.Statistics.Distributions.GumbelDistribution.Cumulant(), FutureTest.FutureTest.CumulantTest(), Test.AdvancedIntegerMathTest.FactorialNegativeArgumentTest(), Test.AdvancedIntegerMathTest.FactorialRecurrence(), Test.AdvancedIntegerMathTest.FactorialSpecialCases(), Test.OrthogonalPolynomialsTest.HermiteOrthonormality(), Test.OrthogonalPolynomialsTest.HermiteSpecialCases(), Test.OrthogonalPolynomialsTest.HermiteSum(), Test.MultiIntegrateTest.IsingIntegrals(), Meta.Numerics.Functions.OrthogonalPolynomials.LegendreP(), Meta.Numerics.Statistics.Distributions.ExponentialDistribution.Moment(), Meta.Numerics.Statistics.Distributions.ExponentialDistribution.MomentAboutMean(), Meta.Numerics.Statistics.Distributions.LogisticDistribution.MomentAboutMean(), Test.PermutationTest.PermutationCount(), Test.AdvancedMathTest.PolyGammaRecurrence(), Test.AdvancedMathTest.PolyGammaRiemann(), Meta.Numerics.Functions.AdvancedMath.PolyLog_BernoulliSum(), Meta.Numerics.Statistics.Distributions.PoissonDistribution.ProbabilityMass(), Meta.Numerics.Functions.AdvancedMath.Psi(), and Test.MultiIntegrateTest.SeperableIntegrals().
|
inlinestatic |
Computes the logrithm of the factorial of an integer.
n | The argument, which must be non-negative. |
This function provides accurate values of ln(n!) even for values of n which would cause n! to overflow.
ArgumentOutOfRangeException | n is negative. |
References Meta.Numerics.Functions.AdvancedMath.LogGamma().
Referenced by Test.OrthogonalPolynomialsTest.AssociatedLegendreOrthonormalityL(), Test.AdvancedIntegerMathTest.FactorialDoubleFactorialRelationship(), Meta.Numerics.Statistics.BinaryContingencyTable.FisherExactTest(), Meta.Numerics.Functions.OrthogonalPolynomials.LegendreP(), Meta.Numerics.Statistics.Sample.MannWhitneyTest(), Meta.Numerics.Statistics.Distributions.PoissonDistribution.ProbabilityMass(), and FutureTest.FutureTest.TestNormalOrderStatistic().
|
inlinestatic |
Computes a binomial coefficient.
n | The upper argument, which must be non-negative. |
m | The lower argument, which must be non-negative and less than or equal to n . |
The binomial coefficient C(n,m) is the coefficient of xm in the expansion of (1+x)n.
C(n,m) can also be given a combinatoric intrepretation as the total number of ways to pick m items from a set of n distinct items.
For example C(4,2) = 6. This can be seen by expanding (1+x)4 = 1 + 4 x + 6 x2 + 4 x3 + x4 and noting that the coefficient of the x2 term is 6. It can also be seen by considering the four-member set (abcd) and noting that there are 6 possible two-member subests: (ab), (ac), (ad), (bc), (bd), (cd).
Pascal's triangle is a classic representation of binomial coefficients.
C(0,0) | |||||||
C(1,0) | C(1,1) | ||||||
C(2,0) | C(2,1) | C(2,2) | |||||
C(3,0) | C(3,1) | C(3,2) | C(3,3) |
The relation of an element in Pascal's triangle to its two parent elements is C(n+1,m) = C(n,m-1) + C(n,m). There are many other relationships among binomial coefficients. Among the most computationally useful is B(n,m+1) = (n-m)/(m+1) B(n,m), which can be used to generate all the binomial coefficients in a row of Pascal's triangle (i.e., all the coefficients for a given order polynomial) starting from an outer values B(n,0) = 1 = B(n,n). If you need a series of binomial coefficients, using a recursion will be more computationally efficient than calling this method for each one. The BinomialCoefficients method provides a fast enumeration of all the binomial coefficients in a given row of Pascal's triangle.
Binomial coefficients are always integers, but we return the result as double because the value can exceed the capacity of an int or even a long for even quite moderate values of n and m.
ArgumentOutOfRangeException | n is negative, or m lies outside [0,n ]. |
Referenced by Test.AdvancedIntegerMathTest.BinomialCoefficientAgreement(), Test.AdvancedIntegerMathTest.BinomialCoefficientInequality(), Test.AdvancedIntegerMathTest.BinomialCoefficientInvalidArgumentTest1(), Test.AdvancedIntegerMathTest.BinomialCoefficientInvalidArgumentTest2(), Test.AdvancedIntegerMathTest.BinomialCoefficientInvalidArgumentTest3(), Test.AdvancedIntegerMathTest.BinomialCoefficientRecurrence(), Test.AdvancedIntegerMathTest.BinomialCoefficientSpecialCases(), Test.SymmetricMatrixTest.CatalanHankelMatrixDeterminant(), Meta.Numerics.Statistics.Distributions.MomentMath.CentralToCumulant(), Test.SquareMatrixTest.CompanionMatrixEigenvalues(), FutureTest.FutureTest.EqualKS(), Test.OrthogonalPolynomialsTest.HermiteAddition(), Test.OrthogonalPolynomialsTest.HermiteSum(), Meta.Numerics.Statistics.Sample.KolmogorovSmirnovTest(), Meta.Numerics.Statistics.Distributions.KolmogorovTwoSampleExactDistribution.LeftInclusiveProbability(), Meta.Numerics.Statistics.Distributions.TriangularDistribution.Moment(), Meta.Numerics.Statistics.Distributions.BinomialDistribution.MomentAboutMean(), Meta.Numerics.Statistics.Distributions.LognormalDistribution.MomentAboutMean(), Meta.Numerics.Statistics.Distributions.TriangularDistribution.MomentAboutMean(), Meta.Numerics.Statistics.Distributions.BinomialDistribution.ProbabilityMass(), Meta.Numerics.Statistics.Distributions.KolmogorovTwoSampleExactDistribution.ProbabilityMass(), and Meta.Numerics.Statistics.Distributions.MomentMath.RawToCumulant().
|
inlinestatic |
Enumerates the binomial coefficients of a given order.
n | The upper argument, which must be non-negative. |
ArgumentOutOfRangeException | n is negative. |
Referenced by Test.AdvancedIntegerMathTest.BinomialCoefficientAgreement(), Test.AdvancedIntegerMathTest.BinomialCoefficientSums(), Meta.Numerics.Functions.AdvancedMath.ComputeBorweinEtaCoefficients(), Meta.Numerics.Statistics.Distributions.PoissonDistribution.ComputePoissonCentralMoments(), Meta.Numerics.Statistics.Distributions.PoissonDistribution.ComputePoissonRawMoments(), and Meta.Numerics.Statistics.Distributions.BinomialDistribution.InverseLeftProbability().
|
inlinestaticprivate |
|
inlinestaticprivate |
References Meta.Numerics.Functions.AdvancedMath.LogGamma().
|
inlinestatic |
Computes the double factorial of the given integer.
n | The argument, which must be positive. |
The double factorial of an integer is the product all integers of the same parity, up to and including the integer. Thus 5! = 5 * 3 * 1 = 15 and 6! = 6 * 4 * 2 = 48.
ArgumentOutOfRangeException | n is negative. |
Referenced by Meta.Numerics.Statistics.Distributions.WaldDistribution.Cumulant(), Test.AdvancedIntegerMathTest.DoubleFactorialSpecialCases(), Meta.Numerics.Statistics.Distributions.NormalDistribution.MomentAboutMean(), and Meta.Numerics.Functions.AdvancedMath.SphericalBesselY_Series().
|
inlinestatic |
Computes the natural logarithm of the double factorial of the given number.
n | The argument. |
ArgumentOutOfRangeException | n is negative. |
Referenced by Test.AdvancedIntegerMathTest.FactorialDoubleFactorialRelationship(), and Meta.Numerics.Functions.AdvancedMath.SphericalBesselJ_Series().
|
inlinestatic |
Computes the given harmonic number.
n | The index of the harmonic number to compute, which must be non-negative. |
Hn is the nth partial sum of the harmonic series.
Since the harmonic series diverges, Hn grows without bound as n increases, but it does so extremely slowly, approximately as log(n).
References Meta.Numerics.Functions.AdvancedMath.EulerGamma, and Meta.Numerics.Functions.AdvancedMath.Psi().
Referenced by FutureTest.FutureTest.BesselY(), FutureTest.FutureTest.BesselY_Series(), Test.AdvancedIntegerMathTest.HarmonicPsiAgreement(), Test.AdvancedIntegerMathTest.HarmonicSpecialCases(), and Meta.Numerics.Functions.AdvancedMath.PolyLog_LogSeries().
|
inlinestatic |
Computes a Fibonacci number.
n | The index of the Fibonacci number to compute, which must be non-negative. |
References Meta.Numerics.Functions.AdvancedMath.GoldenRatio, and Meta.Numerics.MoreMath.Pow().
Referenced by Test.AdvancedIntegerMathTest.FibonacciRecurrence(), and Test.AdvancedIntegerMathTest.FibonacciSpecialCases().
|
inlinestatic |
Computes the given Bernoulli number.
n | The index of the Bernoulli number to compute, which must be non-negative. |
Bn vanishes for all odd n except n=1. For n about 260 or larger, Bn overflows a double.
References Meta.Numerics.Functions.AdvancedMath.RiemannZeta().
Referenced by Meta.Numerics.Statistics.Distributions.DiscreteUniformDistribution.Cumulant(), Meta.Numerics.Statistics.Distributions.UniformDistribution.Cumulant(), Meta.Numerics.Functions.AdvancedMath.PolyLog_BernoulliSum(), and Meta.Numerics.Functions.AdvancedComplexMath.RiemannZeta_EulerMaclaurin().
|
inlinestatic |
Computes the given Bell number.
n | The index of the Bell number to compute, which must be non-negative. |
References Meta.Numerics.MoreMath.Pow().
|
inlinestatic |
Computes the greatest common factor of two integers.
u | The first integer. |
v | The second integer. |
Referenced by Test.AdvancedIntegerMathTest.GcdLcmTest(), Meta.Numerics.Statistics.Distributions.KolmogorovTwoSampleExactDistribution.LeftInclusiveProbability(), FutureTest.FutureTest.PollardRhoFactor(), Meta.Numerics.Statistics.Distributions.KolmogorovTwoSampleExactDistribution.ProbabilityMass(), and FutureTest.FutureTest.TwoSampleKS().
|
inlinestatic |
Computes the least common multiple of two integers.
u | The first integer. |
v | The second integer. |
Referenced by Test.AdvancedIntegerMathTest.GcdLcmTest(), Test.NullDistributionTests.TwoSampleKolmogorovNullDistributionTest(), FutureTest.FutureTest.TwoSampleKS(), and FutureTest.FutureTest.TwoSampleKS2().
|
inlinestatic |
Computes a power of an integer in modular arithmetic.
b | The base, which must be positive. |
e | The exponent, which must be positive. |
m | The modulus, which must be positive. |
Modular exponentiation is used in many number-theory applications, including primality testing, prime factorization, and cryptography.
ArgumentOutOfRangeException | b , e , or m is not positive. |
Referenced by Meta.Numerics.Functions.AdvancedIntegerMath.FactorByPollardsRhoMethod(), FutureTest.FutureTest.PollardRhoFactor(), and Test.AdvancedIntegerMathTest.PowModTest().
|
inlinestatic |
Enumerates all partitions of the given integer
n | The integer to partition, which must be positive. |
Integer partitions are ways to write an integer as a sum of smaller integers. For example, the integer 4 has 5 partitions: 4, 3 + 1, 2 + 2, 2 + 1 + 1, and 1 + 1 + 1 + 1.
Integer partitions appear in combinatoric problems and solutions to problems that may be mapped into combinatoric problems. For example, the terms which appear in Faà di Bruno's formula correspond to integer partitions.
The number of partitions grows very rapidly with n. Since enumerating through partitions does not require us to count them, no overflows will occur even for large values of n . However, completing the enumeration of such a large number of paritions will take a long time, even though our algorithm produces each partition very quickly. For example, there are about two hundred million partitions of the integer 100.
ArgumentOutOfRangeException | n is not positive. |
Referenced by Test.AdvancedIntegerMathTest.IntegerPartitionCounts(), and Test.AdvancedIntegerMathTest.IntegerPartitionSums().
|
inlinestatic |
Determines whether the given integer is prime.
n | The integer, which must be positive. |
Referenced by Test.AdvancedComplexMathTest.ComplexReimannZetaPrimesTest(), Test.AdvancedIntegerMathTest.CountPrimes(), and Test.AdvancedIntegerMathTest.PrimeSpecialCases().
|
inlinestaticprivate |
|
inlinestaticprivate |
|
inlinestaticprivate |
|
staticprivate |
|
staticprivate |