malachite_base/num/arithmetic/
balanced_mod.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::{BalancedMod, BalancedModAssign};
10use crate::num::conversion::traits::WrappingFrom;
11
12macro_rules! impl_balanced_mod_unsigned {
13    ($u:ident, $s:ident) => {
14        impl BalancedMod<$u> for $u {
15            type Output = $s;
16
17            /// Divides a number by another number, returning the balanced remainder: the
18            /// representative of `self` modulo `other` that is closest to zero.
19            ///
20            /// The remainder $r$ satisfies $-y/2 < r \leq y/2$ and $r \equiv x \bmod y$, which
21            /// determine it uniquely. A remainder of exactly $y/2$ is positive, so the result may
22            /// be negative and is returned as the signed type of the same width. It always fits:
23            /// the magnitude never exceeds $y/2$, which is at most half the unsigned maximum.
24            ///
25            /// # Worst-case complexity
26            /// Constant time and additional memory.
27            ///
28            /// # Panics
29            /// Panics if `other` is zero.
30            ///
31            /// # Examples
32            /// See [here](super::balanced_mod#balanced_mod).
33            #[inline]
34            fn balanced_mod(self, other: $u) -> $s {
35                let r = self % other;
36                if r <= other >> 1 {
37                    $s::wrapping_from(r)
38                } else {
39                    // `r - other` is negative and small enough to fit, but the subtraction has to
40                    // happen before the conversion, where it would not
41                    $s::wrapping_from(r.wrapping_sub(other))
42                }
43            }
44        }
45    };
46}
47apply_to_unsigned_signed_pairs!(impl_balanced_mod_unsigned);
48
49macro_rules! impl_balanced_mod_signed {
50    ($t:ident) => {
51        impl BalancedMod<$t> for $t {
52            type Output = $t;
53
54            /// Divides a number by another number, returning the balanced remainder: the
55            /// representative of `self` modulo `other` that is closest to zero.
56            ///
57            /// The remainder $r$ satisfies $-|y|/2 < r \leq |y|/2$ and $r \equiv x \bmod y$, which
58            /// determine it uniquely. A remainder of exactly $|y|/2$ is positive. Only the
59            /// magnitude of `other` matters, so negating it leaves the result unchanged.
60            ///
61            /// # Worst-case complexity
62            /// Constant time and additional memory.
63            ///
64            /// # Panics
65            /// Panics if `other` is zero.
66            ///
67            /// # Examples
68            /// See [here](super::balanced_mod#balanced_mod).
69            #[inline]
70            fn balanced_mod(self, other: $t) -> $t {
71                // Working in the unsigned domain keeps the most negative divisor, whose magnitude
72                // is not representable, from overflowing.
73                let abs_other = other.unsigned_abs();
74                let r = self.unsigned_abs() % abs_other;
75                let r = if self < 0 && r != 0 { abs_other - r } else { r };
76                if r <= abs_other >> 1 {
77                    $t::wrapping_from(r)
78                } else {
79                    $t::wrapping_from(r.wrapping_sub(abs_other))
80                }
81            }
82        }
83
84        impl BalancedModAssign<$t> for $t {
85            /// Divides a number by another number, replacing the first number by the balanced
86            /// remainder: the representative of `self` modulo `other` that is closest to zero.
87            ///
88            /// The remainder $r$ satisfies $-|y|/2 < r \leq |y|/2$; a remainder of exactly $|y|/2$
89            /// is positive.
90            ///
91            /// # Worst-case complexity
92            /// Constant time and additional memory.
93            ///
94            /// # Panics
95            /// Panics if `other` is zero.
96            ///
97            /// # Examples
98            /// See [here](super::balanced_mod#balanced_mod_assign).
99            #[inline]
100            fn balanced_mod_assign(&mut self, other: $t) {
101                *self = self.balanced_mod(other);
102            }
103        }
104    };
105}
106apply_to_signeds!(impl_balanced_mod_signed);
malachite_base/num/arithmetic/balanced_mod.rs

malachite_base/num/arithmetic/
balanced_mod.rs
