malachite_base/num/arithmetic/balanced_mod_power_of_2.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::num::arithmetic::traits::{BalancedModPowerOf2, BalancedModPowerOf2Assign};
10use crate::num::basic::signeds::PrimitiveSigned;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::conversion::traits::{ExactFrom, WrappingFrom};
13
14// The balanced remainder of `x` modulo $2^k$, for $k$ at most the width, as a signed value of the
15// same width. Only the low $k$ bits of `x` matter. The result fits except when $k$ is the width and
16// those bits are exactly $2^{k-1}$, whose balanced remainder is itself.
17fn balanced_mod_power_of_2_low<
18 U: PrimitiveUnsigned + WrappingFrom<S>,
19 S: ExactFrom<U> + PrimitiveSigned + WrappingFrom<U>,
20>(
21 x: U,
22 pow: u64,
23) -> S {
24 if pow == 0 {
25 return S::ZERO;
26 }
27 let r = x.mod_power_of_2(pow);
28 if r <= U::power_of_2(pow - 1) {
29 S::exact_from(r)
30 } else if pow == U::WIDTH {
31 // `r - 2^k` is `r` itself, reinterpreted as negative.
32 S::wrapping_from(r)
33 } else {
34 // `r - 2^k` is negative and fits, but the subtraction has to happen before the conversion.
35 S::wrapping_from(r.wrapping_sub(U::power_of_2(pow)))
36 }
37}
38
39fn balanced_mod_power_of_2_unsigned<
40 U: PrimitiveUnsigned + WrappingFrom<S>,
41 S: ExactFrom<U> + PrimitiveSigned + WrappingFrom<U>,
42>(
43 x: U,
44 pow: u64,
45) -> S {
46 if pow > U::WIDTH {
47 // Every value of the type lies below $2^{k-1}$, so it is its own balanced remainder.
48 S::exact_from(x)
49 } else {
50 balanced_mod_power_of_2_low(x, pow)
51 }
52}
53
54fn balanced_mod_power_of_2_signed<
55 U: PrimitiveUnsigned + WrappingFrom<S>,
56 S: ExactFrom<U> + PrimitiveSigned + WrappingFrom<U>,
57>(
58 x: S,
59 pow: u64,
60) -> S {
61 if pow > S::WIDTH {
62 // Every value of the type lies in $(-2^{k-1}, 2^{k-1}]$, so it is its own balanced
63 // remainder.
64 x
65 } else {
66 // Reducing modulo $2^k$ only looks at the low $k$ bits, which the two's-complement
67 // reinterpretation keeps.
68 balanced_mod_power_of_2_low(U::wrapping_from(x), pow)
69 }
70}
71
72macro_rules! impl_balanced_mod_power_of_2_unsigned {
73 ($u:ident, $s:ident) => {
74 impl BalancedModPowerOf2 for $u {
75 type Output = $s;
76
77 /// Divides a number by $2^k$, returning the balanced remainder: the representative of
78 /// `self` modulo $2^k$ that is closest to zero.
79 ///
80 /// The remainder $r$ satisfies $-2^{k-1} < r \leq 2^{k-1}$ and $r \equiv x \bmod 2^k$,
81 /// which determine it uniquely; for $k = 0$ it is 0. A remainder of exactly $2^{k-1}$
82 /// is positive, so the result may be negative and is returned as the signed type of the
83 /// same width. This is the same as [`balanced_mod`](super::traits::BalancedMod) with
84 /// modulus $2^k$, when $2^k$ fits in the type.
85 ///
86 /// # Worst-case complexity
87 /// Constant time and additional memory.
88 ///
89 /// # Panics
90 /// Panics if the result does not fit in the signed type: if `pow` is `Self::WIDTH` and
91 /// `self` is $2^{W-1}$, or if `pow` is greater than `Self::WIDTH` and `self` is at
92 /// least $2^{W-1}$, where $W$ is `Self::WIDTH`.
93 ///
94 /// # Examples
95 /// See [here](super::balanced_mod_power_of_2#balanced_mod_power_of_2).
96 #[inline]
97 fn balanced_mod_power_of_2(self, pow: u64) -> $s {
98 balanced_mod_power_of_2_unsigned(self, pow)
99 }
100 }
101 };
102}
103apply_to_unsigned_signed_pairs!(impl_balanced_mod_power_of_2_unsigned);
104
105macro_rules! impl_balanced_mod_power_of_2_signed {
106 ($u:ident, $s:ident) => {
107 impl BalancedModPowerOf2 for $s {
108 type Output = $s;
109
110 /// Divides a number by $2^k$, returning the balanced remainder: the representative of
111 /// `self` modulo $2^k$ that is closest to zero.
112 ///
113 /// The remainder $r$ satisfies $-2^{k-1} < r \leq 2^{k-1}$ and $r \equiv x \bmod 2^k$,
114 /// which determine it uniquely; for $k = 0$ it is 0. A remainder of exactly $2^{k-1}$
115 /// is positive. When `pow` is greater than `Self::WIDTH`, every value is its own
116 /// balanced remainder.
117 ///
118 /// # Worst-case complexity
119 /// Constant time and additional memory.
120 ///
121 /// # Panics
122 /// Panics if `pow` is `Self::WIDTH` and `self` is `Self::MIN`, whose balanced remainder
123 /// $2^{W-1}$ does not fit in the type.
124 ///
125 /// # Examples
126 /// See [here](super::balanced_mod_power_of_2#balanced_mod_power_of_2).
127 #[inline]
128 fn balanced_mod_power_of_2(self, pow: u64) -> $s {
129 balanced_mod_power_of_2_signed::<$u, $s>(self, pow)
130 }
131 }
132
133 impl BalancedModPowerOf2Assign for $s {
134 /// Divides a number by $2^k$, replacing it by the balanced remainder: the
135 /// representative of `self` modulo $2^k$ that is closest to zero.
136 ///
137 /// The remainder $r$ satisfies $-2^{k-1} < r \leq 2^{k-1}$; a remainder of exactly
138 /// $2^{k-1}$ is positive.
139 ///
140 /// # Worst-case complexity
141 /// Constant time and additional memory.
142 ///
143 /// # Panics
144 /// Panics if `pow` is `Self::WIDTH` and `self` is `Self::MIN`.
145 ///
146 /// # Examples
147 /// See [here](super::balanced_mod_power_of_2#balanced_mod_power_of_2_assign).
148 #[inline]
149 fn balanced_mod_power_of_2_assign(&mut self, pow: u64) {
150 *self = self.balanced_mod_power_of_2(pow);
151 }
152 }
153 };
154}
155apply_to_unsigned_signed_pairs!(impl_balanced_mod_power_of_2_signed);