malachite_nz/integer/arithmetic/binomial_coefficient.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer::Integer;
10use crate::natural::Natural;
11use malachite_base::num::arithmetic::traits::{BinomialCoefficient, Parity};
12use malachite_base::num::basic::traits::One;
13
14impl BinomialCoefficient for Integer {
15 /// Computes the binomial coefficient of two [`Integer`]s, taking both by value.
16 ///
17 /// The second argument must be non-negative, but the first may be negative. If it is, the
18 /// identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.
19 ///
20 /// $$
21 /// f(n, k) = \\begin{cases}
22 /// \binom{n}{k} & \text{if} \\quad n \geq 0, \\\\
23 /// (-1)^k \binom{-n+k-1}{k} & \text{if} \\quad n < 0.
24 /// \\end{cases}
25 /// $$
26 ///
27 /// # Worst-case complexity
28 /// $T(n, k) = O(nk (\log (nk))^2 \log\log (nk))$
29 ///
30 /// $M(n, k) = O(nk \log (nk))$
31 ///
32 /// where $T$ is time, $M$ is additional memory, $n$ is `n.significant_bits()` (after the
33 /// negative-$n$ identity is applied), and $k$ is the reduced second argument: the cost is that
34 /// of the [`Natural`] binomial coefficient this delegates to.
35 ///
36 /// # Panics
37 /// Panics if $k$ is negative.
38 ///
39 /// # Examples
40 /// ```
41 /// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
42 /// use malachite_base::num::basic::traits::{One, Two, Zero};
43 /// use malachite_nz::integer::Integer;
44 ///
45 /// assert_eq!(
46 /// Integer::binomial_coefficient(Integer::from(4), Integer::ZERO),
47 /// 1
48 /// );
49 /// assert_eq!(
50 /// Integer::binomial_coefficient(Integer::from(4), Integer::ONE),
51 /// 4
52 /// );
53 /// assert_eq!(
54 /// Integer::binomial_coefficient(Integer::from(4), Integer::TWO),
55 /// 6
56 /// );
57 /// assert_eq!(
58 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(3)),
59 /// 4
60 /// );
61 /// assert_eq!(
62 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(4)),
63 /// 1
64 /// );
65 /// assert_eq!(
66 /// Integer::binomial_coefficient(Integer::from(10), Integer::from(5)),
67 /// 252
68 /// );
69 /// assert_eq!(
70 /// Integer::binomial_coefficient(Integer::from(100), Integer::from(50)).to_string(),
71 /// "100891344545564193334812497256"
72 /// );
73 ///
74 /// assert_eq!(
75 /// Integer::binomial_coefficient(Integer::from(-3), Integer::ZERO),
76 /// 1
77 /// );
78 /// assert_eq!(
79 /// Integer::binomial_coefficient(Integer::from(-3), Integer::ONE),
80 /// -3
81 /// );
82 /// assert_eq!(
83 /// Integer::binomial_coefficient(Integer::from(-3), Integer::TWO),
84 /// 6
85 /// );
86 /// assert_eq!(
87 /// Integer::binomial_coefficient(Integer::from(-3), Integer::from(3)),
88 /// -10
89 /// );
90 /// ```
91 fn binomial_coefficient(n: Self, k: Self) -> Self {
92 assert!(k.sign);
93 if n.sign {
94 Self::from(Natural::binomial_coefficient(n.abs, k.abs))
95 } else {
96 let k_abs = k.abs;
97 Self {
98 sign: k_abs.even(),
99 abs: Natural::binomial_coefficient(n.abs + &k_abs - Natural::ONE, k_abs),
100 }
101 }
102 }
103}
104
105impl<'a> BinomialCoefficient<&'a Self> for Integer {
106 /// Computes the binomial coefficient of two [`Integer`]s, taking both by reference.
107 ///
108 /// The second argument must be non-negative, but the first may be negative. If it is, the
109 /// identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.
110 ///
111 /// $$
112 /// f(n, k) = \\begin{cases}
113 /// \binom{n}{k} & \text{if} \\quad n \geq 0, \\\\
114 /// (-1)^k \binom{-n+k-1}{k} & \text{if} \\quad n < 0.
115 /// \\end{cases}
116 /// $$
117 ///
118 /// # Worst-case complexity
119 /// $T(n, k) = O(nk (\log (nk))^2 \log\log (nk))$
120 ///
121 /// $M(n, k) = O(nk \log (nk))$
122 ///
123 /// where $T$ is time, $M$ is additional memory, $n$ is `n.significant_bits()` (after the
124 /// negative-$n$ identity is applied), and $k$ is the reduced second argument: the cost is that
125 /// of the [`Natural`] binomial coefficient this delegates to.
126 ///
127 /// # Panics
128 /// Panics if $k$ is negative.
129 ///
130 /// # Examples
131 /// ```
132 /// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
133 /// use malachite_base::num::basic::traits::{One, Two, Zero};
134 /// use malachite_nz::integer::Integer;
135 ///
136 /// assert_eq!(
137 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::ZERO),
138 /// 1
139 /// );
140 /// assert_eq!(
141 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::ONE),
142 /// 4
143 /// );
144 /// assert_eq!(
145 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::TWO),
146 /// 6
147 /// );
148 /// assert_eq!(
149 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(3)),
150 /// 4
151 /// );
152 /// assert_eq!(
153 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(4)),
154 /// 1
155 /// );
156 /// assert_eq!(
157 /// Integer::binomial_coefficient(&Integer::from(10), &Integer::from(5)),
158 /// 252
159 /// );
160 /// assert_eq!(
161 /// Integer::binomial_coefficient(&Integer::from(100), &Integer::from(50)).to_string(),
162 /// "100891344545564193334812497256"
163 /// );
164 ///
165 /// assert_eq!(
166 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::ZERO),
167 /// 1
168 /// );
169 /// assert_eq!(
170 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::ONE),
171 /// -3
172 /// );
173 /// assert_eq!(
174 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::TWO),
175 /// 6
176 /// );
177 /// assert_eq!(
178 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(3)),
179 /// -10
180 /// );
181 /// ```
182 fn binomial_coefficient(n: &'a Self, k: &'a Self) -> Self {
183 assert!(k.sign);
184 if n.sign {
185 Self::from(Natural::binomial_coefficient(&n.abs, &k.abs))
186 } else {
187 let k_abs = &k.abs;
188 Self {
189 sign: k_abs.even(),
190 abs: Natural::binomial_coefficient(&(&n.abs + k_abs - Natural::ONE), k_abs),
191 }
192 }
193 }
194}