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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
use crate::integer::Integer;
use crate::natural::Natural;
use malachite_base::num::arithmetic::traits::{BinomialCoefficient, Parity};
use malachite_base::num::basic::traits::One;
impl BinomialCoefficient for Integer {
/// Computes the binomial coefficient of two [`Integer`]s, taking both by value.
///
/// The second argument must be non-negative, but the first may be negative. If it is, the
/// identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.
///
/// $$
/// f(n, k) = \\begin{cases}
/// \binom{n}{k} & \text{if} \\quad n \geq 0, \\\\
/// (-1)^k \binom{-n+k-1}{k} & \text{if} \\quad n < 0.
/// \\end{cases}
/// $$
///
/// # Worst-case complexity
/// TODO
///
/// # Panics
/// Panics if $k$ is negative.
///
/// # Examples
/// ```
/// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
/// use malachite_nz::integer::Integer;
///
/// assert_eq!(Integer::binomial_coefficient(Integer::from(4), Integer::from(0)), 1);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(4), Integer::from(1)), 4);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(4), Integer::from(2)), 6);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(4), Integer::from(3)), 4);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(4), Integer::from(4)), 1);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(10), Integer::from(5)), 252);
/// assert_eq!(
/// Integer::binomial_coefficient(Integer::from(100), Integer::from(50)).to_string(),
/// "100891344545564193334812497256"
/// );
///
/// assert_eq!(Integer::binomial_coefficient(Integer::from(-3), Integer::from(0)), 1);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(-3), Integer::from(1)), -3);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(-3), Integer::from(2)), 6);
/// assert_eq!(Integer::binomial_coefficient(Integer::from(-3), Integer::from(3)), -10);
/// ```
fn binomial_coefficient(n: Integer, k: Integer) -> Integer {
assert!(k.sign);
if n.sign {
Integer::from(Natural::binomial_coefficient(n.abs, k.abs))
} else {
let k_abs = k.abs;
Integer {
sign: k_abs.even(),
abs: Natural::binomial_coefficient(n.abs + &k_abs - Natural::ONE, k_abs),
}
}
}
}
impl<'a> BinomialCoefficient<&'a Integer> for Integer {
/// Computes the binomial coefficient of two [`Integer`]s, taking both by reference.
///
/// The second argument must be non-negative, but the first may be negative. If it is, the
/// identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.
///
/// $$
/// f(n, k) = \\begin{cases}
/// \binom{n}{k} & \text{if} \\quad n \geq 0, \\\\
/// (-1)^k \binom{-n+k-1}{k} & \text{if} \\quad n < 0.
/// \\end{cases}
/// $$
///
/// # Worst-case complexity
/// TODO
///
/// # Panics
/// Panics if $k$ is negative.
///
/// # Examples
/// ```
/// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
/// use malachite_nz::integer::Integer;
///
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(4), &Integer::from(0)), 1);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(4), &Integer::from(1)), 4);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(4), &Integer::from(2)), 6);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(4), &Integer::from(3)), 4);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(4), &Integer::from(4)), 1);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(10), &Integer::from(5)), 252);
/// assert_eq!(
/// Integer::binomial_coefficient(&Integer::from(100), &Integer::from(50)).to_string(),
/// "100891344545564193334812497256"
/// );
///
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(0)), 1);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(1)), -3);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(2)), 6);
/// assert_eq!(Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(3)), -10);
/// ```
fn binomial_coefficient(n: &'a Integer, k: &'a Integer) -> Integer {
assert!(k.sign);
if n.sign {
Integer::from(Natural::binomial_coefficient(&n.abs, &k.abs))
} else {
let k_abs = &k.abs;
Integer {
sign: k_abs.even(),
abs: Natural::binomial_coefficient(&(&n.abs + k_abs - Natural::ONE), k_abs),
}
}
}
}