malachite_q/arithmetic/
shr.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::Rational;
10use core::ops::{Shl, ShlAssign, Shr, ShrAssign};
11use malachite_base::num::arithmetic::traits::UnsignedAbs;
12use malachite_base::num::basic::traits::Zero;
13use malachite_base::num::conversion::traits::ExactFrom;
14
15fn shr_unsigned_assign<T>(x: &mut Rational, bits: T)
16where
17    u64: TryFrom<T>,
18{
19    if *x == 0u32 {
20        return;
21    }
22    let numerator_zeros = x.numerator.trailing_zeros().unwrap();
23    let bits_64 = u64::exact_from(bits);
24    if numerator_zeros >= bits_64 {
25        x.numerator >>= bits_64;
26    } else {
27        x.denominator <<= bits_64 - numerator_zeros;
28        x.numerator >>= numerator_zeros;
29    }
30}
31
32fn shr_unsigned_ref<T>(x: &Rational, bits: T) -> Rational
33where
34    u64: TryFrom<T>,
35{
36    if *x == 0u32 {
37        return x.clone();
38    }
39    let numerator_zeros = x.numerator.trailing_zeros().unwrap();
40    let bits_64 = u64::exact_from(bits);
41    if numerator_zeros >= bits_64 {
42        Rational {
43            sign: x.sign,
44            numerator: &x.numerator >> bits_64,
45            denominator: x.denominator.clone(),
46        }
47    } else {
48        Rational {
49            sign: x.sign,
50            numerator: &x.numerator >> numerator_zeros,
51            denominator: &x.denominator << (bits_64 - numerator_zeros),
52        }
53    }
54}
55
56macro_rules! impl_shr_unsigned {
57    ($t:ident) => {
58        impl Shr<$t> for Rational {
59            type Output = Rational;
60
61            /// Right-shifts a [`Rational`] (divides it by a power of 2), taking it by value.
62            ///
63            /// $$
64            /// f(x, k) = \frac{x}{2^k}.
65            /// $$
66            ///
67            /// # Worst-case complexity
68            /// $T(n, m) = O(n + m)$
69            ///
70            /// $M(n, m) = O(n + m)$
71            ///
72            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
73            /// $m$ is `max(bits, 0)`.
74            ///
75            /// See [here](super::shr#shr).
76            #[inline]
77            fn shr(mut self, bits: $t) -> Rational {
78                self >>= bits;
79                self
80            }
81        }
82
83        impl Shr<$t> for &Rational {
84            type Output = Rational;
85
86            /// Right-shifts a [`Rational`] (divides it by a power of 2), taking it by reference.
87            ///
88            /// $$
89            /// f(x, k) = \frac{x}{2^k}.
90            /// $$
91            ///
92            /// # Worst-case complexity
93            /// $T(n, m) = O(n + m)$
94            ///
95            /// $M(n, m) = O(n + m)$
96            ///
97            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
98            /// $m$ is `max(bits, 0)`.
99            ///
100            /// See [here](super::shr#shr).
101            #[inline]
102            fn shr(self, bits: $t) -> Rational {
103                shr_unsigned_ref(self, bits)
104            }
105        }
106
107        impl ShrAssign<$t> for Rational {
108            /// Right-shifts a [`Rational`] (divides it by a power of 2), in place.
109            ///
110            /// $$
111            /// f(x, k) = \frac{x}{2^k}.
112            /// $$
113            ///
114            /// # Worst-case complexity
115            /// $T(n, m) = O(n + m)$
116            ///
117            /// $M(n, m) = O(n + m)$
118            ///
119            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
120            /// $m$ is `max(bits, 0)`.
121            ///
122            /// See [here](super::shr#shr_assign).
123            #[inline]
124            fn shr_assign(&mut self, bits: $t) {
125                shr_unsigned_assign(self, bits);
126            }
127        }
128    };
129}
130apply_to_unsigneds!(impl_shr_unsigned);
131
132fn shr_signed_ref<'a, U, S: Copy + Ord + UnsignedAbs<Output = U> + Zero>(
133    x: &'a Rational,
134    bits: S,
135) -> Rational
136where
137    &'a Rational: Shl<U, Output = Rational> + Shr<U, Output = Rational>,
138{
139    if bits >= S::ZERO {
140        x >> bits.unsigned_abs()
141    } else {
142        x << bits.unsigned_abs()
143    }
144}
145
146fn shr_assign_signed<U, S: Copy + Ord + UnsignedAbs<Output = U> + Zero>(x: &mut Rational, bits: S)
147where
148    Rational: ShlAssign<U> + ShrAssign<U>,
149{
150    if bits >= S::ZERO {
151        *x >>= bits.unsigned_abs();
152    } else {
153        *x <<= bits.unsigned_abs();
154    }
155}
156
157macro_rules! impl_shr_signed {
158    ($t:ident) => {
159        impl Shr<$t> for Rational {
160            type Output = Rational;
161
162            /// Right-shifts a [`Rational`] (divides it by a power of 2), taking it by value.
163            ///
164            /// $$
165            /// f(x, k) = \frac{x}{2^k}.
166            /// $$
167            ///
168            /// # Worst-case complexity
169            /// $T(n, m) = O(n + m)$
170            ///
171            /// $M(n, m) = O(n + m)$
172            ///
173            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
174            /// $m$ is `max(bits, 0)`.
175            ///
176            /// See [here](super::shr#shr).
177            #[inline]
178            fn shr(mut self, bits: $t) -> Rational {
179                self >>= bits;
180                self
181            }
182        }
183
184        impl Shr<$t> for &Rational {
185            type Output = Rational;
186
187            /// Right-shifts a [`Rational`] (divides it by a power of 2), taking it by reference.
188            ///
189            /// $$
190            /// f(x, k) = \frac{x}{2^k}.
191            /// $$
192            ///
193            /// # Worst-case complexity
194            /// $T(n, m) = O(n + m)$
195            ///
196            /// $M(n, m) = O(n + m)$
197            ///
198            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
199            /// $m$ is `max(bits, 0)`.
200            ///
201            /// See [here](super::shr#shr).
202            #[inline]
203            fn shr(self, bits: $t) -> Rational {
204                shr_signed_ref(self, bits)
205            }
206        }
207
208        impl ShrAssign<$t> for Rational {
209            /// Right-shifts a [`Rational`] (divides it by a power of 2), in reference.
210            ///
211            /// $$
212            /// f(x, k) = \frac{x}{2^k}.
213            /// $$
214            ///
215            /// # Worst-case complexity
216            /// $T(n, m) = O(n + m)$
217            ///
218            /// $M(n, m) = O(n + m)$
219            ///
220            /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and
221            /// $m$ is `max(bits, 0)`.
222            ///
223            /// See [here](super::shr#shr_assign).
224            #[inline]
225            fn shr_assign(&mut self, bits: $t) {
226                shr_assign_signed(self, bits)
227            }
228        }
229    };
230}
231apply_to_signeds!(impl_shr_signed);
malachite_q/arithmetic/shr.rs

malachite_q/arithmetic/
shr.rs
