malachite_q/conversion/digits/from_power_of_2_digits.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 alloc::vec::Vec;
11use malachite_base::num::conversion::traits::{ExactFrom, PowerOf2Digits};
12use malachite_base::num::logic::traits::LowMask;
13use malachite_base::rational_sequences::RationalSequence;
14use malachite_nz::natural::Natural;
15
16impl Rational {
17 /// Converts base-$2^k$ digits to a [`Rational`]. The inputs are taken by value.
18 ///
19 /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
20 /// of the fractional portion. The integer-portion digits are ordered from least- to
21 /// most-significant, and the fractional-portion digits from most- to least.
22 ///
23 /// The fractional-portion digits may end in infinitely many zeros or $(2^k-1)$s; these are
24 /// handled correctly.
25 ///
26 /// # Worst-case complexity
27 /// $T(n, m) = O(nm)$
28 ///
29 /// $M(n, m) = O(nm)$
30 ///
31 /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
32 /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
33 ///
34 /// # Panics
35 /// Panics if `log_base` is zero.
36 ///
37 /// # Examples
38 /// ```
39 /// use malachite_base::rational_sequences::RationalSequence;
40 /// use malachite_base::vecs::vec_from_str;
41 /// use malachite_q::Rational;
42 ///
43 /// let before_point = vec_from_str("[1, 1]").unwrap();
44 /// let after_point = RationalSequence::from_vecs(
45 /// vec_from_str("[0]").unwrap(),
46 /// vec_from_str("[0, 0, 1]").unwrap(),
47 /// );
48 /// assert_eq!(
49 /// Rational::from_power_of_2_digits(1, before_point, after_point).to_string(),
50 /// "43/14"
51 /// );
52 ///
53 /// // 21.34565656..._32
54 /// let before_point = vec_from_str("[1, 2]").unwrap();
55 /// let after_point = RationalSequence::from_vecs(
56 /// vec_from_str("[3, 4]").unwrap(),
57 /// vec_from_str("[5, 6]").unwrap(),
58 /// );
59 /// assert_eq!(
60 /// Rational::from_power_of_2_digits(5, before_point, after_point).to_string(),
61 /// "34096673/523776"
62 /// );
63 /// ```
64 pub fn from_power_of_2_digits(
65 log_base: u64,
66 before_point: Vec<Natural>,
67 after_point: RationalSequence<Natural>,
68 ) -> Rational {
69 let (non_repeating, repeating) = after_point.into_vecs();
70 let r_len = u64::exact_from(repeating.len());
71 let nr_len = u64::exact_from(non_repeating.len());
72 let nr =
73 Natural::from_power_of_2_digits_asc(log_base, non_repeating.into_iter().rev()).unwrap();
74 let r = Natural::from_power_of_2_digits_asc(log_base, repeating.into_iter().rev()).unwrap();
75 let floor = Rational::from(
76 Natural::from_power_of_2_digits_asc(log_base, before_point.into_iter()).unwrap(),
77 );
78 floor
79 + if r == 0u32 {
80 Rational::from(nr) >> (log_base * nr_len)
81 } else {
82 (Rational::from_naturals(r, Natural::low_mask(log_base * r_len))
83 + Rational::from(nr))
84 >> (log_base * nr_len)
85 }
86 }
87
88 /// Converts base-$2^k$ digits to a [`Rational`]. The inputs are taken by reference.
89 ///
90 /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
91 /// of the fractional portion. The integer-portion digits are ordered from least- to
92 /// most-significant, and the fractional-portion digits from most- to least.
93 ///
94 /// The fractional-portion digits may end in infinitely many zeros or $(2^k-1)$s; these are
95 /// handled correctly.
96 ///
97 /// # Worst-case complexity
98 /// $T(n, m) = O(nm)$
99 ///
100 /// $M(n, m) = O(nm)$
101 ///
102 /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
103 /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
104 ///
105 /// # Panics
106 /// Panics if `log_base` is zero.
107 ///
108 /// # Examples
109 /// ```
110 /// use malachite_base::rational_sequences::RationalSequence;
111 /// use malachite_base::vecs::vec_from_str;
112 /// use malachite_q::Rational;
113 ///
114 /// let before_point = vec_from_str("[1, 1]").unwrap();
115 /// let after_point = RationalSequence::from_vecs(
116 /// vec_from_str("[0]").unwrap(),
117 /// vec_from_str("[0, 0, 1]").unwrap(),
118 /// );
119 /// assert_eq!(
120 /// Rational::from_power_of_2_digits_ref(1, &before_point, &after_point).to_string(),
121 /// "43/14"
122 /// );
123 ///
124 /// // 21.34565656..._32
125 /// let before_point = vec_from_str("[1, 2]").unwrap();
126 /// let after_point = RationalSequence::from_vecs(
127 /// vec_from_str("[3, 4]").unwrap(),
128 /// vec_from_str("[5, 6]").unwrap(),
129 /// );
130 /// assert_eq!(
131 /// Rational::from_power_of_2_digits_ref(5, &before_point, &after_point).to_string(),
132 /// "34096673/523776"
133 /// );
134 /// ```
135 pub fn from_power_of_2_digits_ref(
136 log_base: u64,
137 before_point: &[Natural],
138 after_point: &RationalSequence<Natural>,
139 ) -> Rational {
140 let (non_repeating, repeating) = after_point.to_vecs();
141 let r_len = u64::exact_from(repeating.len());
142 let nr_len = u64::exact_from(non_repeating.len());
143 let nr =
144 Natural::from_power_of_2_digits_asc(log_base, non_repeating.into_iter().rev()).unwrap();
145 let r = Natural::from_power_of_2_digits_asc(log_base, repeating.into_iter().rev()).unwrap();
146 let floor = Rational::from(
147 Natural::from_power_of_2_digits_asc(log_base, before_point.iter().cloned()).unwrap(),
148 );
149 floor
150 + if r == 0u32 {
151 Rational::from(nr) >> (log_base * nr_len)
152 } else {
153 (Rational::from_naturals(r, Natural::low_mask(log_base * r_len))
154 + Rational::from(nr))
155 >> (log_base * nr_len)
156 }
157 }
158}