malachite_nz/natural/arithmetic/saturating_sub_mul.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::natural::Natural;
10use malachite_base::num::arithmetic::traits::{
11 CheckedSubMul, SaturatingSubMul, SaturatingSubMulAssign,
12};
13use malachite_base::num::basic::traits::Zero;
14
15impl SaturatingSubMul<Self, Self> for Natural {
16 type Output = Self;
17
18 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s, taking all three by value
19 /// and returning 0 if the result is negative.
20 ///
21 /// $$
22 /// f(x, y, z) = \max(x - yz, 0).
23 /// $$
24 ///
25 /// # Worst-case complexity
26 /// $T(n, m) = O(m + n \log n \log\log n)$
27 ///
28 /// $M(n) = O(n \log n)$
29 ///
30 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
31 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
32 ///
33 /// # Examples
34 /// ```
35 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMul};
36 /// use malachite_nz::natural::Natural;
37 ///
38 /// assert_eq!(
39 /// Natural::from(20u32).saturating_sub_mul(Natural::from(3u32), Natural::from(4u32)),
40 /// 8
41 /// );
42 /// assert_eq!(
43 /// Natural::from(10u32).saturating_sub_mul(Natural::from(3u32), Natural::from(4u32)),
44 /// 0
45 /// );
46 /// assert_eq!(
47 /// Natural::from(10u32)
48 /// .pow(12)
49 /// .saturating_sub_mul(Natural::from(0x10000u32), Natural::from(0x10000u32)),
50 /// 995705032704u64
51 /// );
52 /// ```
53 #[inline]
54 fn saturating_sub_mul(self, y: Self, z: Self) -> Self {
55 self.checked_sub_mul(y, z).unwrap_or(Self::ZERO)
56 }
57}
58
59impl SaturatingSubMul<Self, &Self> for Natural {
60 type Output = Self;
61
62 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s, taking the first two by
63 /// value and the third by reference and returning 0 if the result is negative.
64 ///
65 /// $$
66 /// f(x, y, z) = \max(x - yz, 0).
67 /// $$
68 ///
69 /// # Worst-case complexity
70 /// $T(n, m) = O(m + n \log n \log\log n)$
71 ///
72 /// $M(n) = O(n \log n)$
73 ///
74 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
75 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
76 ///
77 /// # Examples
78 /// ```
79 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMul};
80 /// use malachite_nz::natural::Natural;
81 ///
82 /// assert_eq!(
83 /// Natural::from(20u32).saturating_sub_mul(Natural::from(3u32), &Natural::from(4u32)),
84 /// 8
85 /// );
86 /// assert_eq!(
87 /// Natural::from(10u32).saturating_sub_mul(Natural::from(3u32), &Natural::from(4u32)),
88 /// 0
89 /// );
90 /// assert_eq!(
91 /// Natural::from(10u32)
92 /// .pow(12)
93 /// .saturating_sub_mul(Natural::from(0x10000u32), &Natural::from(0x10000u32)),
94 /// 995705032704u64
95 /// );
96 /// ```
97 #[inline]
98 fn saturating_sub_mul(self, y: Self, z: &Self) -> Self {
99 self.checked_sub_mul(y, z).unwrap_or(Self::ZERO)
100 }
101}
102
103impl SaturatingSubMul<&Self, Self> for Natural {
104 type Output = Self;
105
106 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s, taking the first and third
107 /// by value and the second by reference and returning 0 if the result is negative.
108 ///
109 /// $$
110 /// f(x, y, z) = \max(x - yz, 0).
111 /// $$
112 ///
113 /// # Worst-case complexity
114 /// $T(n, m) = O(m + n \log n \log\log n)$
115 ///
116 /// $M(n) = O(n \log n)$
117 ///
118 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
119 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
120 ///
121 /// # Examples
122 /// ```
123 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMul};
124 /// use malachite_nz::natural::Natural;
125 ///
126 /// assert_eq!(
127 /// Natural::from(20u32).saturating_sub_mul(&Natural::from(3u32), Natural::from(4u32)),
128 /// 8
129 /// );
130 /// assert_eq!(
131 /// Natural::from(10u32).saturating_sub_mul(&Natural::from(3u32), Natural::from(4u32)),
132 /// 0
133 /// );
134 /// assert_eq!(
135 /// Natural::from(10u32)
136 /// .pow(12)
137 /// .saturating_sub_mul(&Natural::from(0x10000u32), Natural::from(0x10000u32)),
138 /// 995705032704u64
139 /// );
140 /// ```
141 #[inline]
142 fn saturating_sub_mul(self, y: &Self, z: Self) -> Self {
143 self.checked_sub_mul(y, z).unwrap_or(Self::ZERO)
144 }
145}
146
147impl SaturatingSubMul<&Self, &Self> for Natural {
148 type Output = Self;
149
150 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s, taking the first by value
151 /// and the second and third by reference and returning 0 if the result is negative.
152 ///
153 /// $$
154 /// f(x, y, z) = \max(x - yz, 0).
155 /// $$
156 ///
157 /// # Worst-case complexity
158 /// $T(n, m) = O(m + n \log n \log\log n)$
159 ///
160 /// $M(n) = O(n \log n)$
161 ///
162 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
163 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
164 ///
165 /// # Examples
166 /// ```
167 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMul};
168 /// use malachite_nz::natural::Natural;
169 ///
170 /// assert_eq!(
171 /// Natural::from(20u32).saturating_sub_mul(&Natural::from(3u32), &Natural::from(4u32)),
172 /// 8
173 /// );
174 /// assert_eq!(
175 /// Natural::from(10u32).saturating_sub_mul(&Natural::from(3u32), &Natural::from(4u32)),
176 /// 0
177 /// );
178 /// assert_eq!(
179 /// Natural::from(10u32)
180 /// .pow(12)
181 /// .saturating_sub_mul(&Natural::from(0x10000u32), &Natural::from(0x10000u32)),
182 /// 995705032704u64
183 /// );
184 /// ```
185 #[inline]
186 fn saturating_sub_mul(self, y: &Self, z: &Self) -> Self {
187 self.checked_sub_mul(y, z).unwrap_or(Self::ZERO)
188 }
189}
190
191impl SaturatingSubMul<&Natural, &Natural> for &Natural {
192 type Output = Natural;
193
194 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s, taking all three by
195 /// reference and returning 0 if the result is negative.
196 ///
197 /// $$
198 /// f(x, y, z) = \max(x - yz, 0).
199 /// $$
200 ///
201 /// # Worst-case complexity
202 /// $T(n, m) = O(m + n \log n \log\log n)$
203 ///
204 /// $M(n) = O(n \log n)$
205 ///
206 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
207 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
208 ///
209 /// # Examples
210 /// ```
211 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMul};
212 /// use malachite_nz::natural::Natural;
213 ///
214 /// assert_eq!(
215 /// (&Natural::from(20u32)).saturating_sub_mul(&Natural::from(3u32), &Natural::from(4u32)),
216 /// 8
217 /// );
218 /// assert_eq!(
219 /// (&Natural::from(10u32)).saturating_sub_mul(&Natural::from(3u32), &Natural::from(4u32)),
220 /// 0
221 /// );
222 /// assert_eq!(
223 /// (&Natural::from(10u32).pow(12))
224 /// .saturating_sub_mul(&Natural::from(0x10000u32), &Natural::from(0x10000u32)),
225 /// 995705032704u64
226 /// );
227 /// ```
228 #[inline]
229 fn saturating_sub_mul(self, y: &Natural, z: &Natural) -> Natural {
230 self.checked_sub_mul(y, z).unwrap_or(Natural::ZERO)
231 }
232}
233
234impl SaturatingSubMulAssign<Self, Self> for Natural {
235 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s in place, taking both
236 /// [`Natural`]s on the right-hand side by value and replacing the left-hand side [`Natural`]
237 /// with 0 if the result is negative.
238 ///
239 /// $$
240 /// x \gets \max(x - yz, 0).
241 /// $$
242 ///
243 /// # Worst-case complexity
244 /// $T(n, m) = O(m + n \log n \log\log n)$
245 ///
246 /// $M(n) = O(n \log n)$
247 ///
248 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
249 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
250 ///
251 /// # Examples
252 /// ```
253 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMulAssign};
254 /// use malachite_nz::natural::Natural;
255 ///
256 /// let mut x = Natural::from(20u32);
257 /// x.saturating_sub_mul_assign(Natural::from(3u32), Natural::from(4u32));
258 /// assert_eq!(x, 8);
259 ///
260 /// let mut x = Natural::from(10u32);
261 /// x.saturating_sub_mul_assign(Natural::from(3u32), Natural::from(4u32));
262 /// assert_eq!(x, 0);
263 ///
264 /// let mut x = Natural::from(10u32).pow(12);
265 /// x.saturating_sub_mul_assign(Natural::from(0x10000u32), Natural::from(0x10000u32));
266 /// assert_eq!(x, 995705032704u64);
267 /// ```
268 #[inline]
269 fn saturating_sub_mul_assign(&mut self, y: Self, z: Self) {
270 if self.sub_mul_assign_no_panic(y, z) {
271 *self = Self::ZERO;
272 }
273 }
274}
275
276impl SaturatingSubMulAssign<Self, &Self> for Natural {
277 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s in place, taking the first
278 /// [`Natural`] on the right-hand side by value and the second by reference and replacing the
279 /// left-hand side [`Natural`] with 0 if the result is negative.
280 ///
281 /// $$
282 /// x \gets \max(x - yz, 0).
283 /// $$
284 ///
285 /// # Worst-case complexity
286 /// $T(n, m) = O(m + n \log n \log\log n)$
287 ///
288 /// $M(n) = O(n \log n)$
289 ///
290 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
291 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
292 ///
293 /// # Examples
294 /// ```
295 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMulAssign};
296 /// use malachite_nz::natural::Natural;
297 ///
298 /// let mut x = Natural::from(20u32);
299 /// x.saturating_sub_mul_assign(Natural::from(3u32), &Natural::from(4u32));
300 /// assert_eq!(x, 8);
301 ///
302 /// let mut x = Natural::from(10u32);
303 /// x.saturating_sub_mul_assign(Natural::from(3u32), &Natural::from(4u32));
304 /// assert_eq!(x, 0);
305 ///
306 /// let mut x = Natural::from(10u32).pow(12);
307 /// x.saturating_sub_mul_assign(Natural::from(0x10000u32), &Natural::from(0x10000u32));
308 /// assert_eq!(x, 995705032704u64);
309 /// ```
310 #[inline]
311 fn saturating_sub_mul_assign(&mut self, y: Self, z: &Self) {
312 if self.sub_mul_assign_val_ref_no_panic(y, z) {
313 *self = Self::ZERO;
314 }
315 }
316}
317
318impl SaturatingSubMulAssign<&Self, Self> for Natural {
319 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s in place, taking the first
320 /// [`Natural`] on the right-hand side by reference and the second by value and replacing the
321 /// left-hand side [`Natural`] with 0 if the result is negative.
322 ///
323 /// $$
324 /// x \gets \max(x - yz, 0).
325 /// $$
326 ///
327 /// # Worst-case complexity
328 /// $T(n, m) = O(m + n \log n \log\log n)$
329 ///
330 /// $M(n) = O(n \log n)$
331 ///
332 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
333 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
334 ///
335 /// # Examples
336 /// ```
337 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMulAssign};
338 /// use malachite_nz::natural::Natural;
339 ///
340 /// let mut x = Natural::from(20u32);
341 /// x.saturating_sub_mul_assign(&Natural::from(3u32), Natural::from(4u32));
342 /// assert_eq!(x, 8);
343 ///
344 /// let mut x = Natural::from(10u32);
345 /// x.saturating_sub_mul_assign(&Natural::from(3u32), Natural::from(4u32));
346 /// assert_eq!(x, 0);
347 ///
348 /// let mut x = Natural::from(10u32).pow(12);
349 /// x.saturating_sub_mul_assign(&Natural::from(0x10000u32), Natural::from(0x10000u32));
350 /// assert_eq!(x, 995705032704u64);
351 /// ```
352 #[inline]
353 fn saturating_sub_mul_assign(&mut self, y: &Self, z: Self) {
354 if self.sub_mul_assign_ref_val_no_panic(y, z) {
355 *self = Self::ZERO;
356 }
357 }
358}
359
360impl SaturatingSubMulAssign<&Self, &Self> for Natural {
361 /// Subtracts a [`Natural`] by the product of two other [`Natural`]s in place, taking both
362 /// [`Natural`]s on the right-hand side by reference and replacing the left-hand side
363 /// [`Natural`] with 0 if the result is negative.
364 ///
365 /// $$
366 /// x \gets \max(x - yz, 0).
367 /// $$
368 ///
369 /// # Worst-case complexity
370 /// $T(n, m) = O(m + n \log n \log\log n)$
371 ///
372 /// $M(n) = O(n \log n)$
373 ///
374 /// where $T$ is time, $M$ is additional memory, $n$ is `max(y.significant_bits(),
375 /// z.significant_bits())`, and $m$ is `self.significant_bits()`.
376 ///
377 /// # Examples
378 /// ```
379 /// use malachite_base::num::arithmetic::traits::{Pow, SaturatingSubMulAssign};
380 /// use malachite_nz::natural::Natural;
381 ///
382 /// let mut x = Natural::from(20u32);
383 /// x.saturating_sub_mul_assign(&Natural::from(3u32), &Natural::from(4u32));
384 /// assert_eq!(x, 8);
385 ///
386 /// let mut x = Natural::from(10u32);
387 /// x.saturating_sub_mul_assign(&Natural::from(3u32), &Natural::from(4u32));
388 /// assert_eq!(x, 0);
389 ///
390 /// let mut x = Natural::from(10u32).pow(12);
391 /// x.saturating_sub_mul_assign(&Natural::from(0x10000u32), &Natural::from(0x10000u32));
392 /// assert_eq!(x, 995705032704u64);
393 /// ```
394 #[inline]
395 fn saturating_sub_mul_assign(&mut self, y: &Self, z: &Self) {
396 if self.sub_mul_assign_ref_ref_no_panic(y, z) {
397 *self = Self::ZERO;
398 }
399 }
400}