Comparing algorithms for computing binomial coefficients in Java

I have these 3 different algorithms for computing binomial coefficients (I also had the 4th recursive one, yet I discarded it since it is super slow). The first uses the factorial formula, the second optimizes it a bit, and the last is a dynamic programming algorithm that maintains a Pascal's triangle which reduces the computation to a single addition provided that the triangle is large enough (and if it is not, it is expanded rather efficiently). The formula behind the last algorithm is

$$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}.$$

You can think of the above like that \$n\$ selects the row of the Pascal's triangle (zero-based indexing), and \$k, k - 1\$ select two consecutive entries on a row (also zero-based indexing).

See what I have:

AbstractBinomialCoefficientComputer.java:

package net.coderodde.math;

import java.math.BigInteger;

/**
 * This abstract class defines the API for computing binomial coefficients.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 8, 2016)
 */
public abstract class AbstractBinomialCoefficientComputer {

    /**
     * Computes the binomial coefficient {@code n} over {@code k}.
     * 
     * @param n the number of elements in the set.
     * @param k the number of elements to choose.
     * @return the number of distinct combinations when choosing {@code k} out 
     *         of {@code n} elements.
     */
    public abstract BigInteger compute(final BigInteger n, final BigInteger k);

    protected void checkArguments(final BigInteger n, final BigInteger k) {
        if (n.compareTo(BigInteger.ZERO)  0) {
            throw new IllegalArgumentException(
                    "The 'k' is larger than 'n'. (" + k + " > " + n + ").");
        }
    }

}

FactorialBinomialCoefficientComputer.java:

```
package net.coderodde.math.support;

import java.math.BigInteger;
import net.coderodde.math.AbstractBinomialCoefficientComputer;

/**
* This binomial coefficient computer computes the coefficients by mea

Uses a lot of space

I tried increasing MAXIMUM_N to 2000, and I got this error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Since you are populating Pascal's triangle, you are using \$O(n^2)\$ space, and furthermore, each slot in the triangle is a BigNumber that is getting increasingly bigger with each row, so it's actually around \$O(n^3)\$ space.

Alternative suggestion

I modified your FactorialBinomialCoefficientComputer solution to keep an ArrayList of previously computed factorials. This requires around \$O(n^2)\$ space as opposed to \$O(n^3)\$ space. It isn't quite as fast as the Pascal's triangle version because it needs to do a division + multiply + subtract to compute each answer. But it uses less space and is able to handle larger values of N.

With MAXIMUM_N at 1000 and SIZE at 10000, I got these times:


Seed = 1572945124315246

FactorialBinomialCoefficientComputer in 5405 milliseconds.

MultiplicativeBinomialCoefficientComputer in 2286 milliseconds.

DynamicProgrammingBinomialCoefficientComputer in 166 milliseconds.

CachingFactorialBinomialCoefficientComputer in 437 milliseconds.

With MAXIMUM_N at 2000 and SIZE at 5000, I got these times:


Seed = 1572804057554760

FactorialBinomialCoefficientComputer in 10718 milliseconds.

MultiplicativeBinomialCoefficientComputer in 4387 milliseconds.

(DynamicProgrammingBinomialCoefficientComputer ran out of heap)
CachingFactorialBinomialCoefficientComputer in 900 milliseconds.

StackExchange Code Review Q#134309, answer score: 3