malachite_nz/natural/arithmetic/
mod_power_of_2_neg.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    ModPowerOf2Neg, ModPowerOf2NegAssign, NegModPowerOf2, NegModPowerOf2Assign,
12};
13use malachite_base::num::logic::traits::SignificantBits;
14
15impl ModPowerOf2Neg for Natural {
16    type Output = Self;
17
18    /// Negates a [`Natural`] modulo $2^k$. The input must be already reduced modulo $2^k$. The
19    /// [`Natural`] is taken by value.
20    ///
21    /// $f(x, k) = y$, where $x, y < 2^k$ and $-x \equiv y \mod 2^k$.
22    ///
23    /// # Worst-case complexity
24    /// $T(n) = O(n)$
25    ///
26    /// $M(n) = O(n)$
27    ///
28    /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
29    ///
30    /// # Panics
31    /// Panics if `self` is greater than or equal to $2^k$.
32    ///
33    /// # Examples
34    /// ```
35    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Neg;
36    /// use malachite_base::num::basic::traits::Zero;
37    /// use malachite_nz::natural::Natural;
38    ///
39    /// assert_eq!(Natural::ZERO.mod_power_of_2_neg(5), 0);
40    /// assert_eq!(Natural::ZERO.mod_power_of_2_neg(100), 0);
41    /// assert_eq!(Natural::from(100u32).mod_power_of_2_neg(8), 156);
42    /// assert_eq!(
43    ///     Natural::from(100u32).mod_power_of_2_neg(100).to_string(),
44    ///     "1267650600228229401496703205276"
45    /// );
46    /// ```
47    #[inline]
48    fn mod_power_of_2_neg(mut self, pow: u64) -> Self {
49        assert!(
50            self.significant_bits() <= pow,
51            "self must be reduced mod 2^pow, but {self} >= 2^{pow}"
52        );
53        self.neg_mod_power_of_2_assign(pow);
54        self
55    }
56}
57
58impl ModPowerOf2Neg for &Natural {
59    type Output = Natural;
60
61    /// Negates a [`Natural`] modulo $2^k$. The input must be already reduced modulo $2^k$. The
62    /// [`Natural`] is taken by reference.
63    ///
64    /// $f(x, k) = y$, where $x, y < 2^k$ and $-x \equiv y \mod 2^k$.
65    ///
66    /// # Worst-case complexity
67    /// $T(n) = O(n)$
68    ///
69    /// $M(n) = O(n)$
70    ///
71    /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
72    ///
73    /// # Panics
74    /// Panics if `self` is greater than or equal to $2^k$.
75    ///
76    /// # Examples
77    /// ```
78    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Neg;
79    /// use malachite_base::num::basic::traits::Zero;
80    /// use malachite_nz::natural::Natural;
81    ///
82    /// assert_eq!((&Natural::ZERO).mod_power_of_2_neg(5), 0);
83    /// assert_eq!((&Natural::ZERO).mod_power_of_2_neg(100), 0);
84    /// assert_eq!((&Natural::from(100u32)).mod_power_of_2_neg(8), 156);
85    /// assert_eq!(
86    ///     (&Natural::from(100u32)).mod_power_of_2_neg(100).to_string(),
87    ///     "1267650600228229401496703205276"
88    /// );
89    /// ```
90    #[inline]
91    fn mod_power_of_2_neg(self, pow: u64) -> Natural {
92        assert!(
93            self.significant_bits() <= pow,
94            "self must be reduced mod 2^pow, but {self} >= 2^{pow}"
95        );
96        self.neg_mod_power_of_2(pow)
97    }
98}
99
100impl ModPowerOf2NegAssign for Natural {
101    /// Negates a [`Natural`] modulo $2^k$, in place. The input must be already reduced modulo
102    /// $2^k$.
103    ///
104    /// $x \gets y$, where $x, y < 2^p$ and $-x \equiv y \mod 2^p$.
105    ///
106    /// # Worst-case complexity
107    /// $T(n) = O(n)$
108    ///
109    /// $M(n) = O(n)$
110    ///
111    /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
112    ///
113    /// # Panics
114    /// Panics if `self` is greater than or equal to $2^k$.
115    ///
116    /// # Examples
117    /// ```
118    /// use malachite_base::num::arithmetic::traits::ModPowerOf2NegAssign;
119    /// use malachite_base::num::basic::traits::Zero;
120    /// use malachite_nz::natural::Natural;
121    ///
122    /// let mut n = Natural::ZERO;
123    /// n.mod_power_of_2_neg_assign(5);
124    /// assert_eq!(n, 0);
125    ///
126    /// let mut n = Natural::ZERO;
127    /// n.mod_power_of_2_neg_assign(100);
128    /// assert_eq!(n, 0);
129    ///
130    /// let mut n = Natural::from(100u32);
131    /// n.mod_power_of_2_neg_assign(8);
132    /// assert_eq!(n, 156);
133    ///
134    /// let mut n = Natural::from(100u32);
135    /// n.mod_power_of_2_neg_assign(100);
136    /// assert_eq!(n.to_string(), "1267650600228229401496703205276");
137    /// ```
138    #[inline]
139    fn mod_power_of_2_neg_assign(&mut self, pow: u64) {
140        assert!(
141            self.significant_bits() <= pow,
142            "self must be reduced mod 2^pow, but {self} >= 2^{pow}"
143        );
144        self.neg_mod_power_of_2_assign(pow);
145    }
146}
malachite_nz/natural/arithmetic/mod_power_of_2_neg.rs

malachite_nz/natural/arithmetic/
mod_power_of_2_neg.rs
