malachite_nz/integer/arithmetic/binomial_coefficient.rs
1// Copyright © 2025 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 /// TODO
29 ///
30 /// # Panics
31 /// Panics if $k$ is negative.
32 ///
33 /// # Examples
34 /// ```
35 /// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
36 /// use malachite_nz::integer::Integer;
37 ///
38 /// assert_eq!(
39 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(0)),
40 /// 1
41 /// );
42 /// assert_eq!(
43 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(1)),
44 /// 4
45 /// );
46 /// assert_eq!(
47 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(2)),
48 /// 6
49 /// );
50 /// assert_eq!(
51 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(3)),
52 /// 4
53 /// );
54 /// assert_eq!(
55 /// Integer::binomial_coefficient(Integer::from(4), Integer::from(4)),
56 /// 1
57 /// );
58 /// assert_eq!(
59 /// Integer::binomial_coefficient(Integer::from(10), Integer::from(5)),
60 /// 252
61 /// );
62 /// assert_eq!(
63 /// Integer::binomial_coefficient(Integer::from(100), Integer::from(50)).to_string(),
64 /// "100891344545564193334812497256"
65 /// );
66 ///
67 /// assert_eq!(
68 /// Integer::binomial_coefficient(Integer::from(-3), Integer::from(0)),
69 /// 1
70 /// );
71 /// assert_eq!(
72 /// Integer::binomial_coefficient(Integer::from(-3), Integer::from(1)),
73 /// -3
74 /// );
75 /// assert_eq!(
76 /// Integer::binomial_coefficient(Integer::from(-3), Integer::from(2)),
77 /// 6
78 /// );
79 /// assert_eq!(
80 /// Integer::binomial_coefficient(Integer::from(-3), Integer::from(3)),
81 /// -10
82 /// );
83 /// ```
84 fn binomial_coefficient(n: Integer, k: Integer) -> Integer {
85 assert!(k.sign);
86 if n.sign {
87 Integer::from(Natural::binomial_coefficient(n.abs, k.abs))
88 } else {
89 let k_abs = k.abs;
90 Integer {
91 sign: k_abs.even(),
92 abs: Natural::binomial_coefficient(n.abs + &k_abs - Natural::ONE, k_abs),
93 }
94 }
95 }
96}
97
98impl<'a> BinomialCoefficient<&'a Integer> for Integer {
99 /// Computes the binomial coefficient of two [`Integer`]s, taking both by reference.
100 ///
101 /// The second argument must be non-negative, but the first may be negative. If it is, the
102 /// identity $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ is used.
103 ///
104 /// $$
105 /// f(n, k) = \\begin{cases}
106 /// \binom{n}{k} & \text{if} \\quad n \geq 0, \\\\
107 /// (-1)^k \binom{-n+k-1}{k} & \text{if} \\quad n < 0.
108 /// \\end{cases}
109 /// $$
110 ///
111 /// # Worst-case complexity
112 /// TODO
113 ///
114 /// # Panics
115 /// Panics if $k$ is negative.
116 ///
117 /// # Examples
118 /// ```
119 /// use malachite_base::num::arithmetic::traits::BinomialCoefficient;
120 /// use malachite_nz::integer::Integer;
121 ///
122 /// assert_eq!(
123 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(0)),
124 /// 1
125 /// );
126 /// assert_eq!(
127 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(1)),
128 /// 4
129 /// );
130 /// assert_eq!(
131 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(2)),
132 /// 6
133 /// );
134 /// assert_eq!(
135 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(3)),
136 /// 4
137 /// );
138 /// assert_eq!(
139 /// Integer::binomial_coefficient(&Integer::from(4), &Integer::from(4)),
140 /// 1
141 /// );
142 /// assert_eq!(
143 /// Integer::binomial_coefficient(&Integer::from(10), &Integer::from(5)),
144 /// 252
145 /// );
146 /// assert_eq!(
147 /// Integer::binomial_coefficient(&Integer::from(100), &Integer::from(50)).to_string(),
148 /// "100891344545564193334812497256"
149 /// );
150 ///
151 /// assert_eq!(
152 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(0)),
153 /// 1
154 /// );
155 /// assert_eq!(
156 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(1)),
157 /// -3
158 /// );
159 /// assert_eq!(
160 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(2)),
161 /// 6
162 /// );
163 /// assert_eq!(
164 /// Integer::binomial_coefficient(&Integer::from(-3), &Integer::from(3)),
165 /// -10
166 /// );
167 /// ```
168 fn binomial_coefficient(n: &'a Integer, k: &'a Integer) -> Integer {
169 assert!(k.sign);
170 if n.sign {
171 Integer::from(Natural::binomial_coefficient(&n.abs, &k.abs))
172 } else {
173 let k_abs = &k.abs;
174 Integer {
175 sign: k_abs.even(),
176 abs: Natural::binomial_coefficient(&(&n.abs + k_abs - Natural::ONE), k_abs),
177 }
178 }
179 }
180}