Class Binomial

java.lang.Object
org.bzdev.math.Binomial

public class Binomial extends Object
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) $$

    / n \       / n-1 \      /  n-1 \
    |   |   =  |       |  + |        |
    \ m /       \ m-1 /      \   m  /

to compute multiple values efficiently.

  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    Modifier and Type
    Method
    Description
    static 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

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • Binomial

      public Binomial()
  • Method Details

    • C

      public static long C(int n, int m) throws IllegalArgumentException
      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 relation
           C(n,k) = (n/k)C(n-1,k-1)
       
      and
           C(n,k) = C(n,n-k)
       
      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.
      Parameters:
      n - a non-negative number
      m - 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
           C(n,k) = (n/k)C(n-1,k-1)
       
      and
           C(n,k) = C(n,n-k)
       
      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 the 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 number
      m - 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 number
      m - a non-negative number less than or equal to n
      Returns:
      the logarithm of the binomial coefficient C(n,m)
    • exactC

      public static BigInteger[] exactC(int n)
      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

      public static BigInteger[] exactC(BigInteger[] prev, int n)
      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)