Repository navigation
binomial(n, k) is very slow #68
Description
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
Activity
cuviper commentedon Jan 29, 2025
It is already using that algorithm, but since it's written for generic
T: Integer, it's keeping those iterative values asBigUintin your case, rather than localn: 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 usingBigUint.So I think
num_integer::binomialstill won't be as fast as a bespoke non-generic implementation. Maybe we should move the implementation intoIntegermethods, sonum-bigintcan better optimize this itself.thomasarmel commentedon Jan 29, 2025
Oh ok thanks for the quick response