malachite_q/conversion/digits/to_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::collections::BTreeMap;
11use alloc::vec::Vec;
12use malachite_base::num::arithmetic::traits::{Abs, AbsAssign, Floor, UnsignedAbs};
13use malachite_base::num::conversion::traits::PowerOf2Digits;
14use malachite_base::rational_sequences::RationalSequence;
15use malachite_nz::natural::Natural;
16
17pub(crate) fn to_power_of_2_digits_helper(
18 x: Rational,
19 log_base: u64,
20) -> (Vec<Natural>, RationalSequence<Natural>) {
21 let floor = (&x).floor();
22 let mut remainder = x - Rational::from(&floor);
23 let before_point = floor.unsigned_abs().to_power_of_2_digits_asc(log_base);
24 let mut state_map = BTreeMap::new();
25 let mut digits = Vec::new();
26 for i in 0.. {
27 if remainder == 0u32 {
28 return (before_point, RationalSequence::from_vec(digits));
29 }
30 if let Some(previous_i) = state_map.insert(remainder.clone(), i) {
31 let repeating = digits.drain(previous_i..).collect();
32 return (before_point, RationalSequence::from_vecs(digits, repeating));
33 }
34 remainder <<= log_base;
35 let floor = (&remainder).floor().unsigned_abs();
36 digits.push(floor.clone());
37 remainder -= Rational::from(floor);
38 }
39 unreachable!()
40}
41
42impl Rational {
43 /// Returns the base-$2^k$ digits of a [`Rational`], taking the [`Rational`] by value.
44 ///
45 /// The output has two components. The first is a [`Vec`] of the digits of the integer portion
46 /// of the [`Rational`], least- to most-significant. The second is a [`RationalSequence`] of the
47 /// digits of the fractional portion.
48 ///
49 /// The output is in its simplest form: the integer-portion digits do not end with a zero, and
50 /// the fractional-portion digits do not end with infinitely many zeros or $(2^k-1)$s.
51 ///
52 /// The fractional portion may be very large; the length of the repeating part may be almost as
53 /// large as the denominator. If the [`Rational`] has a large denominator, consider using
54 /// [`power_of_2_digits`](Rational::power_of_2_digits) instead, which returns an iterator. That
55 /// function computes the fractional digits lazily and doesn't need to compute the entire
56 /// repeating part.
57 ///
58 /// # Worst-case complexity
59 /// $T(n, m) = O(m2^n)$
60 ///
61 /// $M(n, m) = O(m2^n)$
62 ///
63 /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and $m$ is
64 /// `log_base`.
65 ///
66 /// # Panics
67 /// Panics if `log_base` is zero.
68 ///
69 /// # Examples
70 /// ```
71 /// use malachite_base::strings::ToDebugString;
72 /// use malachite_q::Rational;
73 ///
74 /// let (before_point, after_point) = Rational::from(3u32).into_power_of_2_digits(1);
75 /// assert_eq!(before_point.to_debug_string(), "[1, 1]");
76 /// assert_eq!(after_point.to_string(), "[]");
77 ///
78 /// let (before_point, after_point) = Rational::from_signeds(22, 7).into_power_of_2_digits(1);
79 /// assert_eq!(before_point.to_debug_string(), "[1, 1]");
80 /// assert_eq!(after_point.to_string(), "[[0, 0, 1]]");
81 ///
82 /// let (before_point, after_point) = Rational::from_signeds(22, 7).into_power_of_2_digits(10);
83 /// assert_eq!(before_point.to_debug_string(), "[3]");
84 /// assert_eq!(after_point.to_string(), "[[146, 292, 585]]");
85 /// ```
86 #[inline]
87 pub fn into_power_of_2_digits(
88 mut self,
89 log_base: u64,
90 ) -> (Vec<Natural>, RationalSequence<Natural>) {
91 self.abs_assign();
92 to_power_of_2_digits_helper(self, log_base)
93 }
94
95 /// Returns the base-$2^k$ digits of a [`Rational`], taking the [`Rational`] by reference.
96 ///
97 /// The output has two components. The first is a [`Vec`] of the digits of the integer portion
98 /// of the [`Rational`], least- to most-significant. The second is a [`RationalSequence`] of the
99 /// digits of the fractional portion.
100 ///
101 /// The output is in its simplest form: the integer-portion digits do not end with a zero, and
102 /// the fractional-portion digits do not end with infinitely many zeros or $(2^k-1)$s.
103 ///
104 /// The fractional portion may be very large; the length of the repeating part may be almost as
105 /// large as the denominator. If the [`Rational`] has a large denominator, consider using
106 /// [`power_of_2_digits`](Rational::power_of_2_digits) instead, which returns an iterator. That
107 /// function computes the fractional digits lazily and doesn't need to compute the entire
108 /// repeating part.
109 ///
110 /// # Worst-case complexity
111 /// $T(n, m) = O(m2^n)$
112 ///
113 /// $M(n, m) = O(m2^n)$
114 ///
115 /// where $T$ is time, $M$ is additional memory, $n$ is `self.significant_bits()`, and $m$ is
116 /// `log_base`.
117 ///
118 /// # Panics
119 /// Panics if `log_base` is zero.
120 ///
121 /// # Examples
122 /// ```
123 /// use malachite_base::strings::ToDebugString;
124 /// use malachite_q::Rational;
125 ///
126 /// let (before_point, after_point) = Rational::from(3u32).to_power_of_2_digits(1);
127 /// assert_eq!(before_point.to_debug_string(), "[1, 1]");
128 /// assert_eq!(after_point.to_string(), "[]");
129 ///
130 /// let (before_point, after_point) = Rational::from_signeds(22, 7).to_power_of_2_digits(1);
131 /// assert_eq!(before_point.to_debug_string(), "[1, 1]");
132 /// assert_eq!(after_point.to_string(), "[[0, 0, 1]]");
133 ///
134 /// let (before_point, after_point) = Rational::from_signeds(22, 7).to_power_of_2_digits(10);
135 /// assert_eq!(before_point.to_debug_string(), "[3]");
136 /// assert_eq!(after_point.to_string(), "[[146, 292, 585]]");
137 /// ```
138 pub fn to_power_of_2_digits(&self, log_base: u64) -> (Vec<Natural>, RationalSequence<Natural>) {
139 to_power_of_2_digits_helper(self.abs(), log_base)
140 }
141}