malachite-nz 0.9.2

The bignum types Natural and Integer, with efficient algorithms partially derived from GMP and FLINT.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::natural::Natural;
use crate::natural::arithmetic::div_round::double_cmp;
use crate::natural::exhaustive::exhaustive_natural_inclusive_range;
use malachite_base::num::arithmetic::traits::{DivExact, Factorial, Gcd, Parity};
use malachite_base::num::basic::traits::{One, Two, Zero};
use malachite_base::num::conversion::traits::ExactFrom;
use std::cmp::Ordering::*;

pub fn binomial_coefficient_naive_1(n: Natural, mut k: Natural) -> Natural {
    if k > n {
        return Natural::ZERO;
    }
    if k == 0u32 || n == k {
        return Natural::ONE;
    }
    if double_cmp(&k, &n) == Greater {
        k = &n - &k;
    }
    let k_u64 = u64::exact_from(&k);
    exhaustive_natural_inclusive_range(&n - k + Natural::ONE, n)
        .product::<Natural>()
        .div_exact(Natural::factorial(k_u64))
}

pub fn binomial_coefficient_naive_2(n: Natural, mut k: Natural) -> Natural {
    if k > n {
        return Natural::ZERO;
    }
    if k == 0u32 || n == k {
        return Natural::ONE;
    }
    if double_cmp(&k, &n) == Greater {
        k = &n - &k;
    }
    if k == 1u32 {
        n
    } else if k == 2u32 {
        (&n >> 1) * (if n.even() { n - Natural::ONE } else { n })
    } else {
        let mut product = n - &k + Natural::ONE;
        let mut numerator = product.clone();
        for i in exhaustive_natural_inclusive_range(Natural::TWO, k) {
            numerator += Natural::ONE;
            let gcd = (&numerator).gcd(&i);
            product /= i.div_exact(&gcd);
            product *= (&numerator).div_exact(gcd);
        }
        product
    }
}