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 ) -> Self {
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 = Self::from(
76 Natural::from_power_of_2_digits_asc(log_base, before_point.into_iter()).unwrap(),
77 );
78 floor
79 + if r == 0u32 {
80 Self::from(nr) >> (log_base * nr_len)
81 } else {
82 (Self::from_naturals(r, Natural::low_mask(log_base * r_len)) + Self::from(nr))
83 >> (log_base * nr_len)
84 }
85 }
86
87 /// Converts base-$2^k$ digits to a [`Rational`]. The inputs are taken by reference.
88 ///
89 /// The input consists of the digits of the integer portion of the [`Rational`] and the digits
90 /// of the fractional portion. The integer-portion digits are ordered from least- to
91 /// most-significant, and the fractional-portion digits from most- to least.
92 ///
93 /// The fractional-portion digits may end in infinitely many zeros or $(2^k-1)$s; these are
94 /// handled correctly.
95 ///
96 /// # Worst-case complexity
97 /// $T(n, m) = O(nm)$
98 ///
99 /// $M(n, m) = O(nm)$
100 ///
101 /// where $T$ is time, $M$ is additional memory, $n$ is `max(before_point.len(),
102 /// after_point.component_len())`, and $m$ is `base.significant_bits()`.
103 ///
104 /// # Panics
105 /// Panics if `log_base` is zero.
106 ///
107 /// # Examples
108 /// ```
109 /// use malachite_base::rational_sequences::RationalSequence;
110 /// use malachite_base::vecs::vec_from_str;
111 /// use malachite_q::Rational;
112 ///
113 /// let before_point = vec_from_str("[1, 1]").unwrap();
114 /// let after_point = RationalSequence::from_vecs(
115 /// vec_from_str("[0]").unwrap(),
116 /// vec_from_str("[0, 0, 1]").unwrap(),
117 /// );
118 /// assert_eq!(
119 /// Rational::from_power_of_2_digits_ref(1, &before_point, &after_point).to_string(),
120 /// "43/14"
121 /// );
122 ///
123 /// // 21.34565656..._32
124 /// let before_point = vec_from_str("[1, 2]").unwrap();
125 /// let after_point = RationalSequence::from_vecs(
126 /// vec_from_str("[3, 4]").unwrap(),
127 /// vec_from_str("[5, 6]").unwrap(),
128 /// );
129 /// assert_eq!(
130 /// Rational::from_power_of_2_digits_ref(5, &before_point, &after_point).to_string(),
131 /// "34096673/523776"
132 /// );
133 /// ```
134 pub fn from_power_of_2_digits_ref(
135 log_base: u64,
136 before_point: &[Natural],
137 after_point: &RationalSequence<Natural>,
138 ) -> Self {
139 let (non_repeating, repeating) = after_point.to_vecs();
140 let r_len = u64::exact_from(repeating.len());
141 let nr_len = u64::exact_from(non_repeating.len());
142 let nr =
143 Natural::from_power_of_2_digits_asc(log_base, non_repeating.into_iter().rev()).unwrap();
144 let r = Natural::from_power_of_2_digits_asc(log_base, repeating.into_iter().rev()).unwrap();
145 let floor = Self::from(
146 Natural::from_power_of_2_digits_asc(log_base, before_point.iter().cloned()).unwrap(),
147 );
148 floor
149 + if r == 0u32 {
150 Self::from(nr) >> (log_base * nr_len)
151 } else {
152 (Self::from_naturals(r, Natural::low_mask(log_base * r_len)) + Self::from(nr))
153 >> (log_base * nr_len)
154 }
155 }
156}