malachite_nz/natural/arithmetic/
mod_add.rs

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

malachite_nz/natural/arithmetic/
mod_add.rs
