java.lang.Object
org.bzdev.math.Binomial
Class for computing binomial coefficients.
The methods are all static. One computes a single binomial coefficient and the others use the equation $$ \left( \begin{array}{c}n \\ m\end{array} \right) = \left( \begin{array}{c}n-1 \\ m-1\end{array} \right) + \left( \begin{array}{c}n-1 \\ m\end{array} \right) $$ to compute multiple values efficiently.
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic long
C
(int n, int m) Compute a binomial coefficient C(n,m).static double
coefficient
(int n, int m) Compute a binomial coefficient C(n,m) as a double-precision number.static long[]
coefficients
(int n) Compute binomial coefficients C(n,m) for all allowed values of m.static BigInteger[]
exactC
(int n) Compute binomial coefficients exactly.static BigInteger[]
exactC
(BigInteger[] prev, int n) Compute binomial coefficients exactly given an array of coefficients.static double
logC
(int n, int m) Compute the natural logarithm of a binomial coefficient
-
Constructor Details
-
Binomial
public Binomial()
-
-
Method Details
-
C
Compute a binomial coefficient C(n,m). The normal notation is $$\left(\begin{array}{c}n \\ m \end{array}\right) = \frac{n!}{m!(n-m)!}$$ The value is computed using the relationC(n,k) = (n/k)C(n-1,k-1)
in order that integer multiplication does not overflow at intermediate steps. The maximum value of n is 64 due to limits on the size of numbers that can be represented as signed 64-bit integers.C(n,k) = C(n,n-k)
- Parameters:
n
- a non-negative numberm
- a non-negative number less than or equal to n- Returns:
- the binomial coefficient C(n,m)
- Throws:
IllegalArgumentException
- an argument is out of range
-
coefficient
public static double coefficient(int n, int m) Compute a binomial coefficient C(n,m) as a double-precision number. The normal notation is $$\left(\begin{array}{c}n \\ m \end{array}\right) = \frac{n!}{m!(n-m)!}$$ The for n < 65, the value is computed using the relation
andC(n,k) = (n/k)C(n-1,k-1)
in order that integer multiplication does not overflow at intermediate steps. For larger values of n, the coefficients cannot be expressed as long integers (signed with 64 bits). For this case, the method uses theC(n,k) = C(n,n-k)
Functions.logFactorial(int)
method to compute exp(log n! - log m! - log (n-m)!).The time complexity of the algorithm is O(1) due to table-look-up being used for small values of n and asymptotic forms for large n
- Parameters:
n
- a non-negative numberm
- a non-negative number less than or equal to n- Returns:
- the binomial coefficient C(n,m)
-
logC
public static double logC(int n, int m) Compute the natural logarithm of a binomial coefficient- Parameters:
n
- a non-negative numberm
- a non-negative number less than or equal to n- Returns:
- the logarithm of the binomial coefficient C(n,m)
-
exactC
Compute binomial coefficients exactly. This method computes binomial coefficients using infinite-precision arithmetic.- Parameters:
n
- the first argument to C(n,m)- Returns:
- an array of length n+1 containing the binomial coefficient C(n,m) at index m
-
exactC
Compute binomial coefficients exactly given an array of coefficients. This method computes binomial coefficients using infinite-precision arithmetic. It is intended for cases where one needs binomial coefficients C(n,m) for consecutive values of n.- Parameters:
prev
- an array whose mth index is C(n-1,m)n
- the first argument to C(n,m)- Returns:
- an array of length n+1 containing the binomial coefficient C(n,m) at index m
-
coefficients
public static long[] coefficients(int n) Compute binomial coefficients C(n,m) for all allowed values of m.- Parameters:
n
- the number of elements- Returns:
- an array whose ith index is C(n,i)
-