malachite_q/arithmetic/log_base_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::{
12 CeilingLogBase2, CeilingLogBasePowerOf2, CheckedLogBase2, CheckedLogBasePowerOf2, DivMod,
13 DivRound, FloorLogBase2, FloorLogBasePowerOf2, Sign,
14};
15use malachite_base::rounding_modes::RoundingMode::*;
16
17impl FloorLogBasePowerOf2<i64> for &Rational {
18 type Output = i64;
19
20 /// Returns the floor of the base-$2^k$ logarithm of a positive [`Rational`].
21 ///
22 /// $k$ may be negative.
23 ///
24 /// $f(x, k) = \lfloor\log_{2^k} x\rfloor$.
25 ///
26 /// # Worst-case complexity
27 /// $T(n) = O(n)$
28 ///
29 /// $M(n) = O(1)$
30 ///
31 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
32 ///
33 /// # Panics
34 /// Panics if `self` is less than or equal to 0 or `pow` is 0.
35 ///
36 /// # Examples
37 /// ```
38 /// use malachite_base::num::arithmetic::traits::FloorLogBasePowerOf2;
39 /// use malachite_q::Rational;
40 ///
41 /// assert_eq!(Rational::from(100).floor_log_base_power_of_2(2), 3);
42 /// assert_eq!(
43 /// Rational::from(4294967296u64).floor_log_base_power_of_2(8),
44 /// 4
45 /// );
46 ///
47 /// // 4^(-2) < 1/10 < 4^(-1)
48 /// assert_eq!(
49 /// Rational::from_signeds(1, 10).floor_log_base_power_of_2(2),
50 /// -2
51 /// );
52 /// // (1/4)^2 < 1/10 < (1/4)^1
53 /// assert_eq!(
54 /// Rational::from_signeds(1, 10).floor_log_base_power_of_2(-2),
55 /// 1
56 /// );
57 /// ```
58 fn floor_log_base_power_of_2(self, pow: i64) -> i64 {
59 assert!(*self > 0u32);
60 match pow.sign() {
61 Equal => panic!("Cannot take base-1 logarithm"),
62 Greater => self.floor_log_base_2().div_round(pow, Floor).0,
63 Less => -(self.ceiling_log_base_2().div_round(-pow, Ceiling).0),
64 }
65 }
66}
67
68impl CeilingLogBasePowerOf2<i64> for &Rational {
69 type Output = i64;
70
71 /// Returns the ceiling of the base-$2^k$ logarithm of a positive [`Rational`].
72 ///
73 /// $k$ may be negative.
74 ///
75 /// $f(x, p) = \lceil\log_{2^p} x\rceil$.
76 ///
77 /// # Worst-case complexity
78 /// $T(n) = O(n)$
79 ///
80 /// $M(n) = O(1)$
81 ///
82 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
83 ///
84 /// # Panics
85 /// Panics if `self` is less than or equal to 0 or `pow` is 0.
86 ///
87 /// # Examples
88 /// ```
89 /// use malachite_base::num::arithmetic::traits::CeilingLogBasePowerOf2;
90 /// use malachite_q::Rational;
91 ///
92 /// assert_eq!(Rational::from(100).ceiling_log_base_power_of_2(2), 4);
93 /// assert_eq!(
94 /// Rational::from(4294967296u64).ceiling_log_base_power_of_2(8),
95 /// 4
96 /// );
97 ///
98 /// // 4^(-2) < 1/10 < 4^(-1)
99 /// assert_eq!(
100 /// Rational::from_signeds(1, 10).ceiling_log_base_power_of_2(2),
101 /// -1
102 /// );
103 /// // (1/4)^2 < 1/10 < (1/4)^1
104 /// assert_eq!(
105 /// Rational::from_signeds(1, 10).ceiling_log_base_power_of_2(-2),
106 /// 2
107 /// );
108 /// ```
109 fn ceiling_log_base_power_of_2(self, pow: i64) -> i64 {
110 assert!(*self > 0u32);
111 match pow.sign() {
112 Equal => panic!("Cannot take base-1 logarithm"),
113 Greater => self.ceiling_log_base_2().div_round(pow, Ceiling).0,
114 Less => -self.floor_log_base_2().div_round(-pow, Floor).0,
115 }
116 }
117}
118
119impl CheckedLogBasePowerOf2<i64> for &Rational {
120 type Output = i64;
121
122 /// Returns the base-$2^k$ logarithm of a positive [`Rational`]. If the [`Rational`] is not a
123 /// power of $2^k$, then `None` is returned.
124 ///
125 /// $k$ may be negative.
126 ///
127 /// $$
128 /// f(x, p) = \\begin{cases}
129 /// \operatorname{Some}(\log_{2^p} x) & \text{if} \\quad \log_{2^p} x \in \Z, \\\\
130 /// \operatorname{None} & \textrm{otherwise}.
131 /// \\end{cases}
132 /// $$
133 ///
134 /// # Worst-case complexity
135 /// $T(n) = O(n)$
136 ///
137 /// $M(n) = O(1)$
138 ///
139 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
140 ///
141 /// # Panics
142 /// Panics if `self` is 0 or `pow` is 0.
143 ///
144 /// # Examples
145 /// ```
146 /// use malachite_base::num::arithmetic::traits::CheckedLogBasePowerOf2;
147 /// use malachite_q::Rational;
148 ///
149 /// assert_eq!(Rational::from(100).checked_log_base_power_of_2(2), None);
150 /// assert_eq!(
151 /// Rational::from(4294967296u64).checked_log_base_power_of_2(8),
152 /// Some(4)
153 /// );
154 ///
155 /// // 4^(-2) < 1/10 < 4^(-1)
156 /// assert_eq!(
157 /// Rational::from_signeds(1, 10).checked_log_base_power_of_2(2),
158 /// None
159 /// );
160 /// assert_eq!(
161 /// Rational::from_signeds(1, 16).checked_log_base_power_of_2(2),
162 /// Some(-2)
163 /// );
164 /// // (1/4)^2 < 1/10 < (1/4)^1
165 /// assert_eq!(
166 /// Rational::from_signeds(1, 10).checked_log_base_power_of_2(-2),
167 /// None
168 /// );
169 /// assert_eq!(
170 /// Rational::from_signeds(1, 16).checked_log_base_power_of_2(-2),
171 /// Some(2)
172 /// );
173 /// ```
174 fn checked_log_base_power_of_2(self, pow: i64) -> Option<i64> {
175 assert!(*self > 0u32);
176 let log_base_2 = self.checked_log_base_2()?;
177 let (pow, neg) = match pow.sign() {
178 Equal => panic!("Cannot take base-1 logarithm"),
179 Greater => (pow, false),
180 Less => (-pow, true),
181 };
182 let (log, rem) = log_base_2.div_mod(pow);
183 if rem != 0 {
184 None
185 } else if neg {
186 Some(-log)
187 } else {
188 Some(log)
189 }
190 }
191}