malachite_nz/natural/arithmetic/
mod_power_of_2_shr.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 core::ops::{Shr, ShrAssign};
11use malachite_base::num::arithmetic::traits::{
12    ModPowerOf2Shl, ModPowerOf2ShlAssign, ModPowerOf2Shr, ModPowerOf2ShrAssign, UnsignedAbs,
13};
14use malachite_base::num::basic::signeds::PrimitiveSigned;
15use malachite_base::num::logic::traits::SignificantBits;
16
17fn mod_power_of_2_shr_ref<'a, U, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
18    x: &'a Natural,
19    bits: S,
20    pow: u64,
21) -> Natural
22where
23    &'a Natural: ModPowerOf2Shl<U, Output = Natural> + Shr<U, Output = Natural>,
24{
25    assert!(
26        x.significant_bits() <= pow,
27        "x must be reduced mod 2^pow, but {x} >= 2^{pow}"
28    );
29    if bits >= S::ZERO {
30        x >> bits.unsigned_abs()
31    } else {
32        x.mod_power_of_2_shl(bits.unsigned_abs(), pow)
33    }
34}
35
36fn mod_power_of_2_shr_assign<U, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
37    x: &mut Natural,
38    bits: S,
39    pow: u64,
40) where
41    Natural: ModPowerOf2ShlAssign<U> + ShrAssign<U>,
42{
43    assert!(
44        x.significant_bits() <= pow,
45        "x must be reduced mod 2^pow, but {x} >= 2^{pow}"
46    );
47    if bits >= S::ZERO {
48        *x >>= bits.unsigned_abs();
49    } else {
50        x.mod_power_of_2_shl_assign(bits.unsigned_abs(), pow);
51    }
52}
53
54macro_rules! impl_mod_power_of_2_shr_signed {
55    ($t:ident) => {
56        impl ModPowerOf2Shr<$t> for Natural {
57            type Output = Natural;
58
59            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$. The
60            /// [`Natural`] must be already reduced modulo $2^k$. The [`Natural`] is taken by value.
61            ///
62            /// $f(x, n, k) = y$, where $x, y < 2^k$ and $\lfloor 2^{-n}x \rfloor \equiv y \mod
63            /// 2^k$.
64            ///
65            /// # Worst-case complexity
66            /// $T(n) = O(n)$
67            ///
68            /// $M(n) = O(n)$
69            ///
70            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
71            ///
72            /// # Panics
73            /// Panics if `self` is greater than or equal to $2^k$.
74            ///
75            /// # Examples
76            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr).
77            #[inline]
78            fn mod_power_of_2_shr(mut self, bits: $t, pow: u64) -> Natural {
79                self.mod_power_of_2_shr_assign(bits, pow);
80                self
81            }
82        }
83
84        impl ModPowerOf2Shr<$t> for &Natural {
85            type Output = Natural;
86
87            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$. The
88            /// [`Natural`] must be already reduced modulo $2^k$. The [`Natural`] is taken by
89            /// reference.
90            ///
91            /// $f(x, n, k) = y$, where $x, y < 2^k$ and $\lfloor 2^{-n}x \rfloor \equiv y \mod
92            /// 2^k$.
93            ///
94            /// # Worst-case complexity
95            /// $T(n) = O(n)$
96            ///
97            /// $M(n) = O(n)$
98            ///
99            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
100            ///
101            /// # Panics
102            /// Panics if `self` is greater than or equal to $2^k$.
103            ///
104            /// # Examples
105            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr).
106            #[inline]
107            fn mod_power_of_2_shr(self, bits: $t, pow: u64) -> Natural {
108                mod_power_of_2_shr_ref(self, bits, pow)
109            }
110        }
111
112        impl ModPowerOf2ShrAssign<$t> for Natural {
113            /// Right-shifts a [`Natural`] (divides it by a power of 2) modulo $2^k$, in place. The
114            /// [`Natural`] must be already reduced modulo $2^k$.
115            ///
116            /// $x \gets y$, where $x, y < 2^k$ and $\lfloor 2^{-n}x \rfloor \equiv y \mod 2^k$.
117            ///
118            /// # Worst-case complexity
119            /// $T(n) = O(n)$
120            ///
121            /// $M(n) = O(n)$
122            ///
123            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
124            ///
125            /// # Panics
126            /// Panics if `self` is greater than or equal to $2^k$.
127            ///
128            /// # Examples
129            /// See [here](super::mod_power_of_2_shr#mod_power_of_2_shr_assign).
130            #[inline]
131            fn mod_power_of_2_shr_assign(&mut self, bits: $t, pow: u64) {
132                mod_power_of_2_shr_assign(self, bits, pow);
133            }
134        }
135    };
136}
137apply_to_signeds!(impl_mod_power_of_2_shr_signed);
malachite_nz/natural/arithmetic/mod_power_of_2_shr.rs

malachite_nz/natural/arithmetic/
mod_power_of_2_shr.rs
