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