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.

Keep the intermediate results and use them instead of recalculating every time you do recursion. — David Soroko, Dec 26 '19 at 14:34
Do not recalculate values you already have, store them instead. — PM 77-1, Dec 26 '19 at 14:34
Have you read [these answers](https://stackoverflow.com/q/12983731/555045)? They're for C# but should be easily adaptable. This recursive algorithm is inherently slow. — harold, Dec 26 '19 at 14:35
I would tend to think that `BigInteger` would be more efficient that `BigDecimal.` — WJS, Dec 26 '19 at 14:51

score 2 · Answer 1 · answered Dec 26 '19 at 14:43

2

Recursion is usually much slower because all function calls must be stored in a stack to allow the return back to the caller functions. In many cases, memory has to be allocated and copied to implement scope isolation.

Try an iterative algorithm like that:

 private static long binomial(int n, int k)
    {
        if (k>n-k)
            k=n-k;

        long b=1;
        for (int i=1, m=n; i<=k; i++, m--)
            b=b*m/i;
        return b;
    }

answered Dec 26 '19 at 14:43

Katy

1,023
7
19

I see, many thanks for the explanation. I assume I can change the int's to BigIntegers as I am calculating very large numbers? – user3607022 Dec 26 '19 at 14:52
The real problem is that implicit factorials should be `memoized` as well as other values. – WJS Dec 26 '19 at 14:52
I can't seem to find the declaration of `m`. – user3607022 Dec 26 '19 at 14:57
1

An int as well. – Katy Dec 26 '19 at 15:00
1

This algorithm is blazingly fast compared to the one I posted. Many thanks for your help! – user3607022 Dec 26 '19 at 18:25
Some background for this solution here: https://stackoverflow.com/questions/12983731/algorithm-for-calculating-binomial-coefficient – David Soroko Dec 27 '19 at 10:21

David Soroko · Accepted Answer · 2019-12-26T19:08:36.950

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
}

Fastest way to calculate binomial coefficients in Java

2 Answers2