malachite_nz/natural/arithmetic/
mod_neg.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::natural::Natural;
10use malachite_base::num::arithmetic::traits::{ModNeg, ModNegAssign};
11use malachite_base::num::basic::traits::Zero;
12
13impl ModNeg<Natural> for Natural {
14    type Output = Natural;
15
16    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
17    /// modulo $m$. Both [`Natural`]s are taken by value.
18    ///
19    /// $f(x, m) = y$, where $x, y < m$ and $-x \equiv y \mod m$.
20    ///
21    /// # Worst-case complexity
22    /// $T(n) = O(n)$
23    ///
24    /// $M(n) = O(1)$
25    ///
26    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
27    ///
28    /// # Panics
29    /// Panics if `self` is greater than or equal to `m`.
30    ///
31    /// # Examples
32    /// ```
33    /// use malachite_base::num::arithmetic::traits::{ModNeg, Pow};
34    /// use malachite_base::num::basic::traits::Zero;
35    /// use malachite_nz::natural::Natural;
36    ///
37    /// assert_eq!(Natural::ZERO.mod_neg(Natural::from(5u32)), 0);
38    /// assert_eq!(Natural::from(7u32).mod_neg(Natural::from(10u32)), 3);
39    /// assert_eq!(
40    ///     Natural::from(7u32).mod_neg(Natural::from(10u32).pow(12)),
41    ///     999999999993u64
42    /// );
43    /// ```
44    #[inline]
45    fn mod_neg(mut self, m: Natural) -> Natural {
46        self.mod_neg_assign(&m);
47        self
48    }
49}
50
51impl<'a> ModNeg<&'a Natural> for Natural {
52    type Output = Natural;
53
54    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
55    /// modulo $m$. The first [`Natural`] is taken by value and the second by reference.
56    ///
57    /// # Worst-case complexity
58    /// $T(n) = O(n)$
59    ///
60    /// $M(n) = O(n)$
61    ///
62    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
63    ///
64    /// # Panics
65    /// Panics if `self` is greater than or equal to `m`.
66    ///
67    /// # Examples
68    /// ```
69    /// use malachite_base::num::arithmetic::traits::{ModNeg, Pow};
70    /// use malachite_base::num::basic::traits::Zero;
71    /// use malachite_nz::natural::Natural;
72    ///
73    /// assert_eq!(Natural::ZERO.mod_neg(&Natural::from(5u32)), 0);
74    /// assert_eq!(Natural::from(7u32).mod_neg(&Natural::from(10u32)), 3);
75    /// assert_eq!(
76    ///     Natural::from(7u32).mod_neg(&Natural::from(10u32).pow(12)),
77    ///     999999999993u64
78    /// );
79    /// ```
80    #[inline]
81    fn mod_neg(mut self, m: &'a Natural) -> Natural {
82        self.mod_neg_assign(m);
83        self
84    }
85}
86
87impl ModNeg<Natural> for &Natural {
88    type Output = Natural;
89
90    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
91    /// modulo $m$. The first [`Natural`] is taken by reference and the second by value.
92    ///
93    /// # Worst-case complexity
94    /// $T(n) = O(n)$
95    ///
96    /// $M(n) = O(1)$
97    ///
98    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
99    ///
100    /// # Panics
101    /// Panics if `self` is greater than or equal to `m`.
102    ///
103    /// # Examples
104    /// ```
105    /// use malachite_base::num::arithmetic::traits::{ModNeg, Pow};
106    /// use malachite_base::num::basic::traits::Zero;
107    /// use malachite_nz::natural::Natural;
108    ///
109    /// assert_eq!((&Natural::ZERO).mod_neg(Natural::from(5u32)), 0);
110    /// assert_eq!((&Natural::from(7u32)).mod_neg(Natural::from(10u32)), 3);
111    /// assert_eq!(
112    ///     (&Natural::from(7u32)).mod_neg(Natural::from(10u32).pow(12)),
113    ///     999999999993u64
114    /// );
115    /// ```
116    fn mod_neg(self, m: Natural) -> Natural {
117        assert!(*self < m, "self must be reduced mod m, but {self} >= {m}");
118        if *self == 0 { Natural::ZERO } else { m - self }
119    }
120}
121
122impl ModNeg<&Natural> for &Natural {
123    type Output = Natural;
124
125    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
126    /// modulo $m$. Both [`Natural`]s are taken by reference.
127    ///
128    /// # Worst-case complexity
129    /// $T(n) = O(n)$
130    ///
131    /// $M(n) = O(n)$
132    ///
133    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
134    ///
135    /// # Panics
136    /// Panics if `self` is greater than or equal to `m`.
137    ///
138    /// # Examples
139    /// ```
140    /// use malachite_base::num::arithmetic::traits::{ModNeg, Pow};
141    /// use malachite_base::num::basic::traits::Zero;
142    /// use malachite_nz::natural::Natural;
143    ///
144    /// assert_eq!((&Natural::ZERO).mod_neg(&Natural::from(5u32)), 0);
145    /// assert_eq!((&Natural::from(7u32)).mod_neg(&Natural::from(10u32)), 3);
146    /// assert_eq!(
147    ///     (&Natural::from(7u32)).mod_neg(&Natural::from(10u32).pow(12)),
148    ///     999999999993u64
149    /// );
150    /// ```
151    fn mod_neg(self, m: &Natural) -> Natural {
152        assert!(self < m, "self must be reduced mod m, but {self} >= {m}");
153        if *self == 0 { Natural::ZERO } else { m - self }
154    }
155}
156
157impl ModNegAssign<Natural> for Natural {
158    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
159    /// modulo $m$. The [`Natural`] on the right-hand side is taken by value.
160    ///
161    /// $x \gets y$, where $x, y < m$ and $-x \equiv y \mod m$.
162    ///
163    /// # Worst-case complexity
164    /// $T(n) = O(n)$
165    ///
166    /// $M(n) = O(1)$
167    ///
168    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
169    ///
170    /// # Panics
171    /// Panics if `self` is greater than or equal to `m`.
172    ///
173    /// # Examples
174    /// ```
175    /// use malachite_base::num::arithmetic::traits::{ModNegAssign, Pow};
176    /// use malachite_base::num::basic::traits::Zero;
177    /// use malachite_nz::natural::Natural;
178    ///
179    /// let mut n = Natural::ZERO;
180    /// n.mod_neg_assign(Natural::from(5u32));
181    /// assert_eq!(n, 0);
182    ///
183    /// let mut n = Natural::from(7u32);
184    /// n.mod_neg_assign(Natural::from(10u32));
185    /// assert_eq!(n, 3);
186    ///
187    /// let mut n = Natural::from(7u32);
188    /// n.mod_neg_assign(Natural::from(10u32).pow(12));
189    /// assert_eq!(n, 999999999993u64);
190    /// ```
191    #[inline]
192    fn mod_neg_assign(&mut self, m: Natural) {
193        self.mod_neg_assign(&m);
194    }
195}
196
197impl<'a> ModNegAssign<&'a Natural> for Natural {
198    /// Negates a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
199    /// modulo $m$. The [`Natural`] on the right-hand side is taken by reference.
200    ///
201    /// $x \gets y$, where $x, y < m$ and $-x \equiv y \mod m$.
202    ///
203    /// # Worst-case complexity
204    /// $T(n) = O(n)$
205    ///
206    /// $M(n) = O(n)$
207    ///
208    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
209    ///
210    /// # Panics
211    /// Panics if `self` is greater than or equal to `m`.
212    ///
213    /// # Examples
214    /// ```
215    /// use malachite_base::num::arithmetic::traits::{ModNegAssign, Pow};
216    /// use malachite_base::num::basic::traits::Zero;
217    /// use malachite_nz::natural::Natural;
218    ///
219    /// let mut n = Natural::ZERO;
220    /// n.mod_neg_assign(&Natural::from(5u32));
221    /// assert_eq!(n, 0);
222    ///
223    /// let mut n = Natural::from(7u32);
224    /// n.mod_neg_assign(&Natural::from(10u32));
225    /// assert_eq!(n, 3);
226    ///
227    /// let mut n = Natural::from(7u32);
228    /// n.mod_neg_assign(&Natural::from(10u32).pow(12));
229    /// assert_eq!(n, 999999999993u64);
230    /// ```
231    fn mod_neg_assign(&mut self, m: &'a Natural) {
232        assert!(&*self < m, "self must be reduced mod m, but {self} >= {m}");
233        if *self != 0 {
234            assert!(!self.sub_right_assign_no_panic(m));
235        }
236    }
237}
malachite_nz/natural/arithmetic/mod_neg.rs

malachite_nz/natural/arithmetic/
mod_neg.rs
