binomial(n, k) is very slow

[thomasarmel]

Hi,
I experienced performance issue with binomial(n, k).

Maybe it could be replaced by the implementation proposed by https://programming-idioms.org/idiom/67/binomial-coefficient-n-choose-k/747/rust

fn binom(n: usize, k: usize) -> BigUint {
    let mut res = BigUint::one();
    for i in 0..k {
        res = (res * BigUint::from(n - i)) /
            BigUint::from(i + 1);
    }
    res
}

Time comparison:

13th Gen Intel(R) Core(TM) i7-13700H, Ubuntu 24.04, rustc 1.84.0, debug

binomial(BigUint::from(401usize), BigUint::from(200usize));

-> 11.921045ms

binom(401, 200);

-> 42.508µs

[cuviper]

It is already using that algorithm, but since it's written for generic T: Integer, it's keeping those iterative values as BigUint in your case, rather than local n: usize, k: usize. I'll bet if you profile this, it will be dominated by heap activity. If so, rust-num/num-bigint#307 would probably help a lot by keeping those small values inline. There's also a GCD to try to avoid overflow, which is irrelevant when using BigUint.

So I think num_integer::binomial still won't be as fast as a bespoke non-generic implementation. Maybe we should move the implementation into Integer methods, so num-bigint can better optimize this itself.

[thomasarmel]

Oh ok thanks for the quick response