malachite_base/num/arithmetic/round_to_multiple_of_power_of_2.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::num::arithmetic::traits::{RoundToMultipleOfPowerOf2, RoundToMultipleOfPowerOf2Assign};
10use crate::num::basic::integers::PrimitiveInt;
11use crate::rounding_modes::RoundingMode;
12use core::cmp::Ordering;
13
14fn round_to_multiple_of_power_of_2<T: PrimitiveInt>(
15 x: T,
16 pow: u64,
17 rm: RoundingMode,
18) -> (T, Ordering) {
19 let (s, o) = x.shr_round(pow, rm);
20 (s.arithmetic_checked_shl(pow).unwrap(), o)
21}
22
23macro_rules! impl_round_to_multiple_of_power_of_2 {
24 ($t:ident) => {
25 impl RoundToMultipleOfPowerOf2<u64> for $t {
26 type Output = $t;
27
28 /// Rounds a number to a multiple of $2^k$ according to a specified rounding mode. An
29 /// [`Ordering`] is also returned, indicating whether the returned value is less than,
30 /// equal to, or greater than the original value.
31 ///
32 /// The only rounding mode that is guaranteed to return without a panic is `Down`.
33 ///
34 /// Let $q = \frac{x}{2^k}$:
35 ///
36 /// $f(x, k, \mathrm{Down}) = 2^k \operatorname{sgn}(q) \lfloor |q| \rfloor.$
37 ///
38 /// $f(x, k, \mathrm{Up}) = 2^k \operatorname{sgn}(q) \lceil |q| \rceil.$
39 ///
40 /// $f(x, k, \mathrm{Floor}) = 2^k \lfloor q \rfloor.$
41 ///
42 /// $f(x, k, \mathrm{Ceiling}) = 2^k \lceil q \rceil.$
43 ///
44 /// $$
45 /// f(x, k, \mathrm{Nearest}) = \begin{cases}
46 /// 2^k \lfloor q \rfloor & \text{if} \\quad
47 /// q - \lfloor q \rfloor < \frac{1}{2} \\\\
48 /// 2^k \lceil q \rceil & \text{if} \\quad q - \lfloor q \rfloor > \frac{1}{2} \\\\
49 /// 2^k \lfloor q \rfloor &
50 /// \text{if} \\quad q - \lfloor q \rfloor =
51 /// \frac{1}{2} \\ \text{and} \\ \lfloor q \rfloor
52 /// \\ \text{is even} \\\\
53 /// 2^k \lceil q \rceil &
54 /// \text{if} \\quad q - \lfloor q \rfloor =
55 /// \frac{1}{2} \\ \text{and} \\ \lfloor q \rfloor \\ \text{is odd.}
56 /// \end{cases}
57 /// $$
58 ///
59 /// $f(x, k, \mathrm{Exact}) = 2^k q$, but panics if $q \notin \Z$.
60 ///
61 /// The following two expressions are equivalent:
62 /// - `x.round_to_multiple_of_power_of_2(pow, Exact)`
63 /// - `{ assert!(x.divisible_by_power_of_2(pow)); x }`
64 ///
65 /// but the latter should be used as it is clearer and more efficient.
66 ///
67 /// # Worst-case complexity
68 /// Constant time and additional memory.
69 ///
70 /// # Panics
71 /// - If `rm` is `Exact`, but `self` is not a multiple of the power of 2.
72 /// - If `rm` is `Floor`, but `self` is negative with a too-large absolute value to
73 /// round to the next lowest multiple.
74 /// - If `rm` is `Ceiling`, but `self` is too large to round to the next highest
75 /// multiple.
76 /// - If `rm` is `Up`, but `self` has too large an absolute value to round to the next
77 /// multiple with a greater absolute value.
78 /// - If `rm` is `Nearest`, but the nearest multiple is outside the representable range.
79 ///
80 /// # Examples
81 /// See [here](super::round_to_multiple_of_power_of_2#round_to_multiple_of_power_of_2).
82 #[inline]
83 fn round_to_multiple_of_power_of_2(self, pow: u64, rm: RoundingMode) -> ($t, Ordering) {
84 round_to_multiple_of_power_of_2(self, pow, rm)
85 }
86 }
87
88 impl RoundToMultipleOfPowerOf2Assign<u64> for $t {
89 /// Rounds a number to a multiple of $2^k$ in place, according to a specified rounding
90 /// mode. An [`Ordering`] is returned, indicating whether the returned value is less
91 /// than, equal to, or greater than the original value.
92 ///
93 /// The only rounding mode that is guaranteed to return without a panic is `Down`.
94 ///
95 /// See the [`RoundToMultipleOfPowerOf2`] documentation for details.
96 ///
97 /// The following two expressions are equivalent:
98 /// - `x.round_to_multiple_of_power_of_2_assign(pow, Exact);`
99 /// - `assert!(x.divisible_by_power_of_2(pow));`
100 ///
101 /// but the latter should be used as it is clearer and more efficient.
102 ///
103 /// # Worst-case complexity
104 /// Constant time and additional memory.
105 ///
106 /// # Panics
107 /// - If `rm` is `Exact`, but `self` is not a multiple of the power of 2.
108 /// - If `rm` is `Floor`, but `self` is negative with a too-large absolute value to
109 /// round to the next lowest multiple.
110 /// - If `rm` is `Ceiling`, but `self` is too large to round to the next highest
111 /// multiple.
112 /// - If `rm` is `Up`, but `self` has too large an absolute value to round to the next
113 /// multiple with a greater absolute value.
114 /// - If `rm` is `Nearest`, but the nearest multiple is outside the representable range.
115 ///
116 /// # Examples
117 /// See
118 /// [here](super::round_to_multiple_of_power_of_2#round_to_multiple_of_power_of_2_assign).
119 #[inline]
120 fn round_to_multiple_of_power_of_2_assign(
121 &mut self,
122 pow: u64,
123 rm: RoundingMode,
124 ) -> Ordering {
125 let o;
126 (*self, o) = self.round_to_multiple_of_power_of_2(pow, rm);
127 o
128 }
129 }
130 };
131}
132apply_to_primitive_ints!(impl_round_to_multiple_of_power_of_2);