malachite_q/arithmetic/
next_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::Rational;
10use core::cmp::Ordering::*;
11use malachite_base::num::arithmetic::traits::{NextPowerOf2, NextPowerOf2Assign, PowerOf2};
12use malachite_base::num::conversion::traits::ExactFrom;
13use malachite_base::num::logic::traits::SignificantBits;
14
15impl NextPowerOf2 for Rational {
16    type Output = Rational;
17
18    /// Finds the smallest power of 2 greater than or equal to a [`Rational`]. The [`Rational`] is
19    /// taken by value.
20    ///
21    /// $f(x) = 2^{\lceil \log_2 x \rceil}$.
22    ///
23    /// # Worst-case complexity
24    /// $T(n) = O(n)$
25    ///
26    /// $M(n) = O(n)$
27    ///
28    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
29    ///
30    /// # Panics
31    /// Panics if `self` is less than or equal to zero.
32    ///
33    /// # Examples
34    /// ```
35    /// use malachite_base::num::arithmetic::traits::NextPowerOf2;
36    /// use malachite_q::Rational;
37    ///
38    /// assert_eq!(Rational::from(123).next_power_of_2(), 128);
39    /// assert_eq!(
40    ///     Rational::from_signeds(1, 10).next_power_of_2().to_string(),
41    ///     "1/8"
42    /// );
43    /// ```
44    #[inline]
45    fn next_power_of_2(self) -> Rational {
46        assert!(self > 0);
47        let mut exponent = i64::exact_from(self.numerator.significant_bits())
48            - i64::exact_from(self.denominator.significant_bits());
49        match self.numerator.cmp_normalized(&self.denominator) {
50            Equal => return self,
51            Greater => exponent += 1,
52            _ => {}
53        }
54        Rational::power_of_2(exponent)
55    }
56}
57
58impl NextPowerOf2 for &Rational {
59    type Output = Rational;
60
61    /// Finds the smallest power of 2 greater than or equal to a [`Rational`]. The [`Rational`] is
62    /// taken by reference.
63    ///
64    /// $f(x) = 2^{\lceil \log_2 x \rceil}$.
65    ///
66    /// # Worst-case complexity
67    /// $T(n) = O(n)$
68    ///
69    /// $M(n) = O(n)$
70    ///
71    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
72    ///
73    /// # Panics
74    /// Panics if `self` is less than or equal to zero.
75    ///
76    /// # Examples
77    /// ```
78    /// use malachite_base::num::arithmetic::traits::NextPowerOf2;
79    /// use malachite_q::Rational;
80    ///
81    /// assert_eq!((&Rational::from(123)).next_power_of_2(), 128);
82    /// assert_eq!(
83    ///     (&Rational::from_signeds(1, 10))
84    ///         .next_power_of_2()
85    ///         .to_string(),
86    ///     "1/8"
87    /// );
88    /// ```
89    fn next_power_of_2(self) -> Rational {
90        assert!(*self > 0);
91        let mut exponent = i64::exact_from(self.numerator.significant_bits())
92            - i64::exact_from(self.denominator.significant_bits());
93        if self.numerator.cmp_normalized(&self.denominator) == Greater {
94            exponent += 1;
95        }
96        Rational::power_of_2(exponent)
97    }
98}
99
100impl NextPowerOf2Assign for Rational {
101    /// Finds the smallest power of 2 greater than or equal to a [`Rational`]. The [`Rational`] is
102    /// taken by reference.
103    ///
104    /// $f(x) = 2^{\lceil \log_2 x \rceil}$.
105    ///
106    /// # Worst-case complexity
107    /// $T(n) = O(n)$
108    ///
109    /// $M(n) = O(n)$
110    ///
111    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
112    ///
113    /// # Panics
114    /// Panics if `self` is less than or equal to zero.
115    ///
116    /// # Examples
117    /// ```
118    /// use malachite_base::num::arithmetic::traits::NextPowerOf2Assign;
119    /// use malachite_q::Rational;
120    ///
121    /// let mut x = Rational::from(123);
122    /// x.next_power_of_2_assign();
123    /// assert_eq!(x, 128);
124    ///
125    /// let mut x = Rational::from_signeds(1, 10);
126    /// x.next_power_of_2_assign();
127    /// assert_eq!(x.to_string(), "1/8");
128    /// ```
129    #[inline]
130    fn next_power_of_2_assign(&mut self) {
131        *self = (&*self).next_power_of_2();
132    }
133}
malachite_q/arithmetic/next_power_of_2.rs

malachite_q/arithmetic/
next_power_of_2.rs
