Fastest way to calculate binomial coefficients in Java

Question

I'm calculating binomial coefficients of arbitrary size using the following recursive function

private static final BigDecimal ZERO = new BigDecimal("0");
private static final BigDecimal ONE = new BigDecimal("1");


private static BigDecimal binomial(BigDecimal n, BigDecimal k) {
     if(n.equals(k) || k.equals(ZERO))
          return ONE;
     else if(k.compareTo(ZERO) < 0)
          return ZERO;
     else
          return binomial(n.subtract(ONE), k).add(binomial(n.subtract(ONE), k.subtract(ONE)));
}

For large numbers it gets really slow. Are there any simple and/or obvious optimizations to make? Not sure how much BigDecimals slows it down but making a custom class for large numbers seems like a lot of work.

Answer 1

You can do reasonably well while keeping the recursion (arithmetics on BigInteger are pretty unpleasant though):

public class Binomials {
    private HashMap<Pair<BigInteger, BigInteger>, BigInteger> map = new HashMap();

    public BigInteger binomial(int n, int k) {
        return binomial(new Pair(valueOf(n), valueOf(k)));
    }

    public BigInteger binomial(Pair<BigInteger, BigInteger> x) {
        if(x.getValue().equals(ZERO) || x.getKey().equals(x.getValue())) {
            return ONE;
        }
        return map.computeIfAbsent(x, nk -> binomial(doP1(nk)).add(binomial(doP2(nk))));
    }

    private Pair<BigInteger, BigInteger> doP1(Pair<BigInteger, BigInteger> nk) {
        return new Pair(nk.getKey().subtract(ONE), nk.getValue());
    }
    private Pair<BigInteger, BigInteger> doP2(Pair<BigInteger, BigInteger> nk) {
        return new Pair(nk.getKey().subtract(ONE), nk.getValue().subtract(ONE));
    }

    public static void main(String[] args) {
        System.out.println(new Binomials().binomial(8, 4)); // 70
    }
}

In fact all the Pair and BigInteger shenanigans are noisy enough to obscure what is going on so here is the same approach in Kotlin:

fun BigInteger.plus(other: BigInteger): BigInteger = this.add(other)
fun BigInteger.minus(other: BigInteger): BigInteger = this.subtract(other)

object Binomial {
    val map = mutableMapOf<Pair<BigInteger, BigInteger>, BigInteger>()

    fun binomial(n: Int, k: Int): BigInteger =
        binomial(Pair(n.toBigInteger(), k.toBigInteger()))


    fun binomial(x: Pair<BigInteger, BigInteger>): BigInteger {
        val (n, k) = x
        if (k == ZERO || n == k) {
            return ONE
        }
        return map.getOrPut(x) { binomial(Pair(n - ONE, k)) + binomial(Pair(n - ONE, k - ONE)) }
    }
}

fun main() {
    println(binomial(8, 4)) // 70
}