malachite_nz/natural/arithmetic/mod_sub.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::{ModSub, ModSubAssign};
11
12impl ModSub<Self, Self> for Natural {
13 type Output = Self;
14
15 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
16 /// reduced modulo $m$. All three [`Natural`]s are taken by value.
17 ///
18 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
19 ///
20 /// # Worst-case complexity
21 /// $T(n) = O(n)$
22 ///
23 /// $M(n) = O(n)$
24 ///
25 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
26 ///
27 /// # Panics
28 /// Panics if `self` or `other` are greater than or equal to `m`.
29 ///
30 /// # Examples
31 /// ```
32 /// use malachite_base::num::arithmetic::traits::ModSub;
33 /// use malachite_nz::natural::Natural;
34 ///
35 /// assert_eq!(
36 /// Natural::from(4u32)
37 /// .mod_sub(Natural::from(3u32), Natural::from(5u32))
38 /// .to_string(),
39 /// "1"
40 /// );
41 /// assert_eq!(
42 /// Natural::from(7u32)
43 /// .mod_sub(Natural::from(9u32), Natural::from(10u32))
44 /// .to_string(),
45 /// "8"
46 /// );
47 /// ```
48 ///
49 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b`, `c`,
50 /// and `m` are taken by value.
51 #[inline]
52 fn mod_sub(mut self, other: Self, m: Self) -> Self {
53 self.mod_sub_assign(other, m);
54 self
55 }
56}
57
58impl ModSub<Self, &Self> for Natural {
59 type Output = Self;
60
61 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
62 /// reduced modulo $m$. The first two [`Natural`]s are taken by value and the third by
63 /// reference.
64 ///
65 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
66 ///
67 /// # Worst-case complexity
68 /// $T(n) = O(n)$
69 ///
70 /// $M(n) = O(n)$
71 ///
72 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
73 ///
74 /// # Panics
75 /// Panics if `self` or `other` are greater than or equal to `m`.
76 ///
77 /// # Examples
78 /// ```
79 /// use malachite_base::num::arithmetic::traits::ModSub;
80 /// use malachite_nz::natural::Natural;
81 ///
82 /// assert_eq!(
83 /// Natural::from(4u32)
84 /// .mod_sub(Natural::from(3u32), &Natural::from(5u32))
85 /// .to_string(),
86 /// "1"
87 /// );
88 /// assert_eq!(
89 /// Natural::from(7u32)
90 /// .mod_sub(Natural::from(9u32), &Natural::from(10u32))
91 /// .to_string(),
92 /// "8"
93 /// );
94 /// ```
95 ///
96 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `c`
97 /// are taken by value and `m` is taken by reference.
98 #[inline]
99 fn mod_sub(mut self, other: Self, m: &Self) -> Self {
100 self.mod_sub_assign(other, m);
101 self
102 }
103}
104
105impl ModSub<&Self, Self> for Natural {
106 type Output = Self;
107
108 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
109 /// reduced modulo $m$. The first and third [`Natural`]s are taken by value and the second by
110 /// reference.
111 ///
112 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
113 ///
114 /// # Worst-case complexity
115 /// $T(n) = O(n)$
116 ///
117 /// $M(n) = O(n)$
118 ///
119 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
120 ///
121 /// # Panics
122 /// Panics if `self` or `other` are greater than or equal to `m`.
123 ///
124 /// # Examples
125 /// ```
126 /// use malachite_base::num::arithmetic::traits::ModSub;
127 /// use malachite_nz::natural::Natural;
128 ///
129 /// assert_eq!(
130 /// Natural::from(4u32)
131 /// .mod_sub(&Natural::from(3u32), Natural::from(5u32))
132 /// .to_string(),
133 /// "1"
134 /// );
135 /// assert_eq!(
136 /// Natural::from(7u32)
137 /// .mod_sub(&Natural::from(9u32), Natural::from(10u32))
138 /// .to_string(),
139 /// "8"
140 /// );
141 /// ```
142 ///
143 /// This isequivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `m`
144 /// are taken by value and `c` is taken by reference.
145 #[inline]
146 fn mod_sub(mut self, other: &Self, m: Self) -> Self {
147 self.mod_sub_assign(other, m);
148 self
149 }
150}
151
152impl ModSub<&Self, &Self> for Natural {
153 type Output = Self;
154
155 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
156 /// reduced modulo $m$. The first [`Natural`] is taken by value and the second and third by
157 /// reference.
158 ///
159 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
160 ///
161 /// # Worst-case complexity
162 /// $T(n) = O(n)$
163 ///
164 /// $M(n) = O(n)$
165 ///
166 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
167 ///
168 /// # Panics
169 /// Panics if `self` or `other` are greater than or equal to `m`.
170 ///
171 /// # Examples
172 /// ```
173 /// use malachite_base::num::arithmetic::traits::ModSub;
174 /// use malachite_nz::natural::Natural;
175 ///
176 /// assert_eq!(
177 /// Natural::from(4u32)
178 /// .mod_sub(&Natural::from(3u32), &Natural::from(5u32))
179 /// .to_string(),
180 /// "1"
181 /// );
182 /// assert_eq!(
183 /// Natural::from(7u32)
184 /// .mod_sub(&Natural::from(9u32), &Natural::from(10u32))
185 /// .to_string(),
186 /// "8"
187 /// );
188 /// ```
189 ///
190 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` is
191 /// taken by value and `c` and `m` are taken by reference.
192 #[inline]
193 fn mod_sub(mut self, other: &Self, m: &Self) -> Self {
194 self.mod_sub_assign(other, m);
195 self
196 }
197}
198
199impl ModSub<Natural, Natural> for &Natural {
200 type Output = Natural;
201
202 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
203 /// reduced modulo $m$. The first [`Natural`] is taken by reference and the second and third by
204 /// value.
205 ///
206 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
207 ///
208 /// # Worst-case complexity
209 /// $T(n) = O(n)$
210 ///
211 /// $M(n) = O(n)$
212 ///
213 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
214 ///
215 /// # Panics
216 /// Panics if `self` or `other` are greater than or equal to `m`.
217 ///
218 /// # Examples
219 /// ```
220 /// use malachite_base::num::arithmetic::traits::ModSub;
221 /// use malachite_nz::natural::Natural;
222 ///
223 /// assert_eq!(
224 /// (&Natural::from(4u32))
225 /// .mod_sub(Natural::from(3u32), Natural::from(5u32))
226 /// .to_string(),
227 /// "1"
228 /// );
229 /// assert_eq!(
230 /// (&Natural::from(7u32))
231 /// .mod_sub(Natural::from(9u32), Natural::from(10u32))
232 /// .to_string(),
233 /// "8"
234 /// );
235 /// ```
236 ///
237 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` is
238 /// taken by reference and `c` and `m` are taken by value.
239 fn mod_sub(self, other: Natural, m: Natural) -> Natural {
240 assert!(*self < m, "self must be reduced mod m, but {self} >= {m}");
241 assert!(other < m, "other must be reduced mod m, but {other} >= {m}");
242 if *self >= other {
243 self - other
244 } else {
245 m - other + self
246 }
247 }
248}
249
250impl ModSub<Natural, &Natural> for &Natural {
251 type Output = Natural;
252
253 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
254 /// reduced modulo $m$. The first and third [`Natural`]s are taken by reference and the second
255 /// by value.
256 ///
257 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
258 ///
259 /// # Worst-case complexity
260 /// $T(n) = O(n)$
261 ///
262 /// $M(n) = O(n)$
263 ///
264 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
265 ///
266 /// # Panics
267 /// Panics if `self` or `other` are greater than or equal to `m`.
268 ///
269 /// # Examples
270 /// ```
271 /// use malachite_base::num::arithmetic::traits::ModSub;
272 /// use malachite_nz::natural::Natural;
273 ///
274 /// assert_eq!(
275 /// (&Natural::from(4u32))
276 /// .mod_sub(Natural::from(3u32), &Natural::from(5u32))
277 /// .to_string(),
278 /// "1"
279 /// );
280 /// assert_eq!(
281 /// (&Natural::from(7u32))
282 /// .mod_sub(Natural::from(9u32), &Natural::from(10u32))
283 /// .to_string(),
284 /// "8"
285 /// );
286 /// ```
287 ///
288 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `m`
289 /// are taken by reference and `c` is taken by value.
290 fn mod_sub(self, other: Natural, m: &Natural) -> Natural {
291 assert!(self < m, "self must be reduced mod m, but {self} >= {m}");
292 assert!(
293 other < *m,
294 "other must be reduced mod m, but {other} >= {m}"
295 );
296 if *self >= other {
297 self - other
298 } else {
299 m - other + self
300 }
301 }
302}
303
304impl ModSub<&Natural, Natural> for &Natural {
305 type Output = Natural;
306
307 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
308 /// reduced modulo $m$. The first two [`Natural`]s are taken by reference and the third by
309 /// value.
310 ///
311 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
312 ///
313 /// # Worst-case complexity
314 /// $T(n) = O(n)$
315 ///
316 /// $M(n) = O(n)$
317 ///
318 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
319 ///
320 /// # Panics
321 /// Panics if `self` or `other` are greater than or equal to `m`.
322 ///
323 /// # Examples
324 /// ```
325 /// use malachite_base::num::arithmetic::traits::ModSub;
326 /// use malachite_nz::natural::Natural;
327 ///
328 /// assert_eq!(
329 /// (&Natural::from(4u32))
330 /// .mod_sub(&Natural::from(3u32), Natural::from(5u32))
331 /// .to_string(),
332 /// "1"
333 /// );
334 /// assert_eq!(
335 /// (&Natural::from(7u32))
336 /// .mod_sub(&Natural::from(9u32), Natural::from(10u32))
337 /// .to_string(),
338 /// "8"
339 /// );
340 /// ```
341 ///
342 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `c`
343 /// are taken by reference and `m` is taken by value.
344 fn mod_sub(self, other: &Natural, m: Natural) -> Natural {
345 assert!(*self < m, "self must be reduced mod m, but {self} >= {m}");
346 assert!(
347 *other < m,
348 "other must be reduced mod m, but {other} >= {m}"
349 );
350 if self >= other {
351 self - other
352 } else {
353 m - other + self
354 }
355 }
356}
357
358impl ModSub<&Natural, &Natural> for &Natural {
359 type Output = Natural;
360
361 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$. The inputs must be already
362 /// reduced modulo $m$. All three [`Natural`]s are taken by reference.
363 ///
364 /// $f(x, y, m) = z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
365 ///
366 /// # Worst-case complexity
367 /// $T(n) = O(n)$
368 ///
369 /// $M(n) = O(n)$
370 ///
371 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
372 ///
373 /// # Panics
374 /// Panics if `self` or `other` are greater than or equal to `m`.
375 ///
376 /// # Examples
377 /// ```
378 /// use malachite_base::num::arithmetic::traits::ModSub;
379 /// use malachite_nz::natural::Natural;
380 ///
381 /// assert_eq!(
382 /// (&Natural::from(4u32))
383 /// .mod_sub(&Natural::from(3u32), &Natural::from(5u32))
384 /// .to_string(),
385 /// "1"
386 /// );
387 /// assert_eq!(
388 /// (&Natural::from(7u32))
389 /// .mod_sub(&Natural::from(9u32), &Natural::from(10u32))
390 /// .to_string(),
391 /// "8"
392 /// );
393 /// ```
394 ///
395 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b`, `c`,
396 /// and `m` are taken by reference.
397 fn mod_sub(self, other: &Natural, m: &Natural) -> Natural {
398 assert!(self < m, "self must be reduced mod m, but {self} >= {m}");
399 assert!(other < m, "other must be reduced mod m, but {other} >= {m}");
400 if self >= other {
401 self - other
402 } else {
403 m - other + self
404 }
405 }
406}
407
408impl ModSubAssign<Self, Self> for Natural {
409 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$, in place. The inputs must be
410 /// already reduced modulo $m$. Both [`Natural`]s on the right-hand side are taken by value.
411 ///
412 /// $x \gets z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
413 ///
414 /// # Worst-case complexity
415 /// $T(n) = O(n)$
416 ///
417 /// $M(n) = O(n)$
418 ///
419 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
420 ///
421 /// # Panics
422 /// Panics if `self` or `other` are greater than or equal to `m`.
423 ///
424 /// # Examples
425 /// ```
426 /// use malachite_base::num::arithmetic::traits::ModSubAssign;
427 /// use malachite_nz::natural::Natural;
428 ///
429 /// let mut x = Natural::from(4u32);
430 /// x.mod_sub_assign(Natural::from(3u32), Natural::from(5u32));
431 /// assert_eq!(x.to_string(), "1");
432 ///
433 /// let mut x = Natural::from(7u32);
434 /// x.mod_sub_assign(Natural::from(9u32), Natural::from(10u32));
435 /// assert_eq!(x.to_string(), "8");
436 /// ```
437 ///
438 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b`, `c`,
439 /// and `m` are taken by value and `a == b`.
440 fn mod_sub_assign(&mut self, other: Self, m: Self) {
441 assert!(*self < m, "self must be reduced mod m, but {self} >= {m}");
442 assert!(other < m, "other must be reduced mod m, but {other} >= {m}");
443 if *self >= other {
444 *self -= other;
445 } else {
446 *self += m - other;
447 }
448 }
449}
450
451impl ModSubAssign<Self, &Self> for Natural {
452 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$, in place. The inputs must be
453 /// already reduced modulo $m$. The first [`Natural`] on the right-hand side is taken by value
454 /// and the second by reference.
455 ///
456 /// $x \gets z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
457 ///
458 /// # Worst-case complexity
459 /// $T(n) = O(n)$
460 ///
461 /// $M(n) = O(n)$
462 ///
463 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
464 ///
465 /// # Panics
466 /// Panics if `self` or `other` are greater than or equal to `m`.
467 ///
468 /// # Examples
469 /// ```
470 /// use malachite_base::num::arithmetic::traits::ModSubAssign;
471 /// use malachite_nz::natural::Natural;
472 ///
473 /// let mut x = Natural::from(4u32);
474 /// x.mod_sub_assign(Natural::from(3u32), &Natural::from(5u32));
475 /// assert_eq!(x.to_string(), "1");
476 ///
477 /// let mut x = Natural::from(7u32);
478 /// x.mod_sub_assign(Natural::from(9u32), &Natural::from(10u32));
479 /// assert_eq!(x.to_string(), "8");
480 /// ```
481 ///
482 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `c`
483 /// are taken by value, `m` is taken by reference, and `a == b`.
484 fn mod_sub_assign(&mut self, other: Self, m: &Self) {
485 assert!(&*self < m, "self must be reduced mod m, but {self} >= {m}");
486 assert!(
487 other < *m,
488 "other must be reduced mod m, but {other} >= {m}"
489 );
490 if *self >= other {
491 *self -= other;
492 } else {
493 *self += m - other;
494 }
495 }
496}
497
498impl ModSubAssign<&Self, Self> for Natural {
499 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$, in place. The inputs must be
500 /// already reduced modulo $m$. The first [`Natural`] on the right-hand side is taken by
501 /// reference and the second by value.
502 ///
503 /// $x \gets z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
504 ///
505 /// # Worst-case complexity
506 /// $T(n) = O(n)$
507 ///
508 /// $M(n) = O(n)$
509 ///
510 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
511 ///
512 /// # Panics
513 /// Panics if `self` or `other` are greater than or equal to `m`.
514 ///
515 /// # Examples
516 /// ```
517 /// use malachite_base::num::arithmetic::traits::ModSubAssign;
518 /// use malachite_nz::natural::Natural;
519 ///
520 /// let mut x = Natural::from(4u32);
521 /// x.mod_sub_assign(&Natural::from(3u32), Natural::from(5u32));
522 /// assert_eq!(x.to_string(), "1");
523 ///
524 /// let mut x = Natural::from(7u32);
525 /// x.mod_sub_assign(&Natural::from(9u32), Natural::from(10u32));
526 /// assert_eq!(x.to_string(), "8");
527 /// ```
528 ///
529 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` and `m`
530 /// are taken by value, `c` is taken by reference, and `a == b`.
531 fn mod_sub_assign(&mut self, other: &Self, m: Self) {
532 assert!(*self < m, "self must be reduced mod m, but {self} >= {m}");
533 assert!(
534 *other < m,
535 "other must be reduced mod m, but {other} >= {m}"
536 );
537 if *self >= *other {
538 *self -= other;
539 } else {
540 *self += m - other;
541 }
542 }
543}
544
545impl ModSubAssign<&Self, &Self> for Natural {
546 /// Subtracts two [`Natural`]s modulo a third [`Natural`] $m$, in place. The inputs must be
547 /// already reduced modulo $m$. Both [`Natural`]s on the right-hand side are taken by reference.
548 ///
549 /// $x \gets z$, where $x, y, z < m$ and $x - y \equiv z \mod m$.
550 ///
551 /// # Worst-case complexity
552 /// $T(n) = O(n)$
553 ///
554 /// $M(n) = O(n)$
555 ///
556 /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
557 ///
558 /// # Panics
559 /// Panics if `self` or `other` are greater than or equal to `m`.
560 ///
561 /// # Examples
562 /// ```
563 /// use malachite_base::num::arithmetic::traits::ModSubAssign;
564 /// use malachite_nz::natural::Natural;
565 ///
566 /// let mut x = Natural::from(4u32);
567 /// x.mod_sub_assign(&Natural::from(3u32), &Natural::from(5u32));
568 /// assert_eq!(x.to_string(), "1");
569 ///
570 /// let mut x = Natural::from(7u32);
571 /// x.mod_sub_assign(&Natural::from(9u32), &Natural::from(10u32));
572 /// assert_eq!(x.to_string(), "8");
573 /// ```
574 ///
575 /// This is equivalent to `_fmpz_mod_subN` from `fmpz_mod/sub.c`, FLINT 2.7.1, where `b` is
576 /// taken by value, `c` and `m` are taken by reference, and `a == b`.
577 fn mod_sub_assign(&mut self, other: &Self, m: &Self) {
578 assert!(&*self < m, "self must be reduced mod m, but {self} >= {m}");
579 assert!(other < m, "other must be reduced mod m, but {other} >= {m}");
580 if *self >= *other {
581 *self -= other;
582 } else {
583 *self += m - other;
584 }
585 }
586}