malachite_base/num/arithmetic/
mod_add.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// Uses code adopted from the FLINT Library.
4//
5//      Copyright © 2010 William Hart
6//
7//      Copyright © 2021 Fredrik Johansson
8//
9// This file is part of Malachite.
10//
11// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
12// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
13// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
14
15use crate::num::arithmetic::traits::{ModAdd, ModAddAssign};
16use crate::num::basic::unsigneds::PrimitiveUnsigned;
17
18fn mod_add<T: PrimitiveUnsigned>(x: T, y: T, m: T) -> T {
19    assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
20    assert!(y < m, "y must be reduced mod m, but {y} >= {m}");
21    let neg = m - x;
22    if neg > y { x + y } else { y - neg }
23}
24
25fn mod_add_assign<T: PrimitiveUnsigned>(x: &mut T, y: T, m: T) {
26    assert!(*x < m, "x must be reduced mod m, but {x} >= {m}");
27    assert!(y < m, "y must be reduced mod m, but {y} >= {m}");
28    let neg = m - *x;
29    if neg > y {
30        *x += y;
31    } else {
32        *x = y - neg;
33    }
34}
35
36macro_rules! impl_mod_add {
37    ($t:ident) => {
38        impl ModAdd<$t> for $t {
39            type Output = $t;
40
41            /// Adds two numbers modulo a third number $m$. The inputs must be already reduced
42            /// modulo $m$.
43            ///
44            /// $f(x, y, m) = z$, where $x, y, z < m$ and $x + y \equiv z \mod m$.
45            ///
46            /// # Worst-case complexity
47            /// Constant time and additional memory.
48            ///
49            /// # Panics
50            /// Panics if `self` or `other` are greater than or equal to `m`.
51            ///
52            /// # Examples
53            /// See [here](super::mod_add#mod_add).
54            ///
55            /// This is equivalent to `nmod_add` from `nmod.h`, FLINT 2.7.1.
56            #[inline]
57            fn mod_add(self, other: $t, m: $t) -> $t {
58                mod_add(self, other, m)
59            }
60        }
61
62        impl ModAddAssign<$t> for $t {
63            /// Adds two numbers modulo a third number $m$, in place. The inputs must be already
64            /// reduced modulo $m$.
65            ///
66            /// $x \gets z$, where $x, y, z < m$ and $x + y \equiv z \mod m$.
67            ///
68            /// # Worst-case complexity
69            /// Constant time and additional memory.
70            ///
71            /// # Panics
72            /// Panics if `self` or `other` are greater than or equal to `m`.
73            ///
74            /// # Examples
75            /// See [here](super::mod_add#mod_add_assign).
76            ///
77            /// This is equivalent to `nmod_add` from `nmod.h`, FLINT 2.7.1, where the result is
78            /// assigned to `a`.
79            #[inline]
80            fn mod_add_assign(&mut self, other: $t, m: $t) {
81                mod_add_assign(self, other, m);
82            }
83        }
84    };
85}
86apply_to_unsigneds!(impl_mod_add);
malachite_base/num/arithmetic/mod_add.rs

malachite_base/num/arithmetic/
mod_add.rs
