IGLib  1.7.2
The IGLib base library EXTENDED - with other lilbraries and applications.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Events Macros
Meta.Numerics.Functions.AdvancedIntegerMath Class Reference

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)
 

Detailed Description

Contains methods that compute advanced functions of integer arguments.

Member Function Documentation

static long [] Meta.Numerics.Functions.AdvancedIntegerMath.CreateFactorialTable ( int  n)
inlinestaticprivate
static double Meta.Numerics.Functions.AdvancedIntegerMath.Factorial ( int  n)
inlinestatic

Computes the factorial of an integer.

Parameters
nThe argument, which must be non-negative.
Returns
The value of n!.

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 &#x393; function (AdvancedMath.Gamma(double)).

Exceptions
ArgumentOutOfRangeExceptionn is negative.
See also
LogFactorial, AdvancedMath.Gamma(double)

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().

static double Meta.Numerics.Functions.AdvancedIntegerMath.LogFactorial ( int  n)
inlinestatic

Computes the logrithm of the factorial of an integer.

Parameters
nThe argument, which must be non-negative.
Returns
The value of ln(n!).

This function provides accurate values of ln(n!) even for values of n which would cause n! to overflow.

Exceptions
ArgumentOutOfRangeExceptionn is negative.
See also
Factorial

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().

static double Meta.Numerics.Functions.AdvancedIntegerMath.BinomialCoefficient ( int  n,
int  m 
)
inlinestatic

Computes a binomial coefficient.

Parameters
nThe upper argument, which must be non-negative.
mThe lower argument, which must be non-negative and less than or equal to n .
Returns
The binomial coefficent C(n ,m ), also denoted "<paramref name="n"/> choose <paramref name="m"/>".

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.

Exceptions
ArgumentOutOfRangeExceptionn 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().

static IEnumerable<double> Meta.Numerics.Functions.AdvancedIntegerMath.BinomialCoefficients ( int  n)
inlinestatic
static long Meta.Numerics.Functions.AdvancedIntegerMath.DoubleFactorial_Multiply ( int  n)
inlinestaticprivate
static double Meta.Numerics.Functions.AdvancedIntegerMath.LogDoubleFactorial_Gamma ( int  n)
inlinestaticprivate
static double Meta.Numerics.Functions.AdvancedIntegerMath.DoubleFactorial ( int  n)
inlinestatic

Computes the double factorial of the given integer.

Parameters
nThe argument, which must be positive.
Returns
The value of n!!.

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.

Exceptions
ArgumentOutOfRangeExceptionn 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().

static double Meta.Numerics.Functions.AdvancedIntegerMath.LogDoubleFactorial ( int  n)
inlinestatic

Computes the natural logarithm of the double factorial of the given number.

Parameters
nThe argument.
Returns
The value of ln(n!!).
Exceptions
ArgumentOutOfRangeExceptionn is negative.
See also
DoubleFactorial

Referenced by Test.AdvancedIntegerMathTest.FactorialDoubleFactorialRelationship(), and Meta.Numerics.Functions.AdvancedMath.SphericalBesselJ_Series().

static double Meta.Numerics.Functions.AdvancedIntegerMath.HarmonicNumber ( int  n)
inlinestatic

Computes the given harmonic number.

Parameters
nThe index of the harmonic number to compute, which must be non-negative.
Returns
The harmonic number Hn.

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().

static double Meta.Numerics.Functions.AdvancedIntegerMath.FibonacciNumber ( int  n)
inlinestatic

Computes a Fibonacci number.

Parameters
nThe index of the Fibonacci number to compute, which must be non-negative.
Returns
The nth Fibonacci number Fn.

References Meta.Numerics.Functions.AdvancedMath.GoldenRatio, and Meta.Numerics.MoreMath.Pow().

Referenced by Test.AdvancedIntegerMathTest.FibonacciRecurrence(), and Test.AdvancedIntegerMathTest.FibonacciSpecialCases().

static double Meta.Numerics.Functions.AdvancedIntegerMath.BernoulliNumber ( int  n)
inlinestatic

Computes the given Bernoulli number.

Parameters
nThe index of the Bernoulli number to compute, which must be non-negative.
Returns
The Bernoulli number Bn.

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().

static double Meta.Numerics.Functions.AdvancedIntegerMath.BellNumber ( int  n)
inlinestatic

Computes the given Bell number.

Parameters
nThe index of the Bell number to compute, which must be non-negative.
Returns
The Bell number Bn.

References Meta.Numerics.MoreMath.Pow().

static long Meta.Numerics.Functions.AdvancedIntegerMath.GCF ( long  u,
long  v 
)
inlinestatic
static long Meta.Numerics.Functions.AdvancedIntegerMath.LCM ( long  u,
long  v 
)
inlinestatic

Computes the least common multiple of two integers.

Parameters
uThe first integer.
vThe second integer.
Returns
The least common multiple of u and v .
See also
GCF

Referenced by Test.AdvancedIntegerMathTest.GcdLcmTest(), Test.NullDistributionTests.TwoSampleKolmogorovNullDistributionTest(), FutureTest.FutureTest.TwoSampleKS(), and FutureTest.FutureTest.TwoSampleKS2().

static int Meta.Numerics.Functions.AdvancedIntegerMath.PowMod ( int  b,
int  e,
int  m 
)
inlinestatic

Computes a power of an integer in modular arithmetic.

Parameters
bThe base, which must be positive.
eThe exponent, which must be positive.
mThe modulus, which must be positive.
Returns
The value of be mod m.

Modular exponentiation is used in many number-theory applications, including primality testing, prime factorization, and cryptography.

Exceptions
ArgumentOutOfRangeExceptionb , e , or m is not positive.

Referenced by Meta.Numerics.Functions.AdvancedIntegerMath.FactorByPollardsRhoMethod(), FutureTest.FutureTest.PollardRhoFactor(), and Test.AdvancedIntegerMathTest.PowModTest().

static IEnumerable<int[]> Meta.Numerics.Functions.AdvancedIntegerMath.Partitions ( int  n)
inlinestatic

Enumerates all partitions of the given integer

Parameters
nThe integer to partition, which must be positive.
Returns
An enumeration of all partitions of the given integer.

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.

Exceptions
ArgumentOutOfRangeExceptionn is not positive.

Referenced by Test.AdvancedIntegerMathTest.IntegerPartitionCounts(), and Test.AdvancedIntegerMathTest.IntegerPartitionSums().

static bool Meta.Numerics.Functions.AdvancedIntegerMath.IsPrime ( int  n)
inlinestatic

Determines whether the given integer is prime.

Parameters
nThe integer, which must be positive.
Returns
True if the integer is prime, otherwise false.

Referenced by Test.AdvancedComplexMathTest.ComplexReimannZetaPrimesTest(), Test.AdvancedIntegerMathTest.CountPrimes(), and Test.AdvancedIntegerMathTest.PrimeSpecialCases().

static bool Meta.Numerics.Functions.AdvancedIntegerMath.IsProbablyPrime ( int  n,
int  m,
int  s,
int  d,
int  w 
)
inlinestaticprivate
static void Meta.Numerics.Functions.AdvancedIntegerMath.FactorByTrialDivision ( List< Factor >  factors,
ref int  n 
)
inlinestaticprivate
static void Meta.Numerics.Functions.AdvancedIntegerMath.FactorByPollardsRhoMethod ( List< Factor >  factors,
ref int  n 
)
inlinestaticprivate

Member Data Documentation

readonly long [] Meta.Numerics.Functions.AdvancedIntegerMath.factorialTable = CreateFactorialTable(20)
staticprivate
readonly double Meta.Numerics.Functions.AdvancedIntegerMath.LogLongMax = Math.Log(Int64.MaxValue)
staticprivate

The documentation for this class was generated from the following file: