malachite_base/num/conversion/digits/general_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::num::basic::unsigneds::PrimitiveUnsigned;
10use crate::num::conversion::traits::{
11 ConvertibleFrom, Digits, ExactFrom, PowerOf2Digits, WrappingFrom,
12};
13use alloc::vec::Vec;
14use itertools::Itertools;
15
16pub_test! {unsigned_to_digits_asc_naive<
17 T: ExactFrom<U> + PrimitiveUnsigned,
18 U: PrimitiveUnsigned + WrappingFrom<T>,
19>(
20 x: &T,
21 base: U,
22) -> Vec<U> {
23 assert!(base > U::ONE);
24 let mut digits = Vec::new();
25 let mut remainder = *x;
26 let base = T::exact_from(base);
27 while remainder != T::ZERO {
28 digits.push(U::wrapping_from(remainder.div_assign_mod(base)));
29 }
30 digits
31}}
32
33fn to_digits_asc<
34 T: ConvertibleFrom<U> + ExactFrom<U> + PrimitiveUnsigned + PowerOf2Digits<U>,
35 U: PrimitiveUnsigned + WrappingFrom<T>,
36>(
37 x: &T,
38 base: &U,
39) -> Vec<U> {
40 assert!(T::convertible_from(*base));
41 if *x == T::ZERO {
42 Vec::new()
43 } else if let Some(log_base) = base.checked_log_base_2() {
44 x.to_power_of_2_digits_asc(log_base)
45 } else {
46 unsigned_to_digits_asc_naive(x, *base)
47 }
48}
49
50fn to_digits_desc<
51 T: ConvertibleFrom<U> + ExactFrom<U> + PrimitiveUnsigned + PowerOf2Digits<U>,
52 U: PrimitiveUnsigned + WrappingFrom<T>,
53>(
54 x: &T,
55 base: &U,
56) -> Vec<U> {
57 assert!(T::convertible_from(*base));
58 if *x == T::ZERO {
59 Vec::new()
60 } else if let Some(log_base) = base.checked_log_base_2() {
61 x.to_power_of_2_digits_desc(log_base)
62 } else {
63 let mut digits = unsigned_to_digits_asc_naive(x, *base);
64 digits.reverse();
65 digits
66 }
67}
68
69fn from_digits_asc<
70 T: Digits<U> + PowerOf2Digits<U>,
71 U: PrimitiveUnsigned,
72 I: Iterator<Item = U>,
73>(
74 base: &U,
75 digits: I,
76) -> Option<T> {
77 if let Some(log_base) = base.checked_log_base_2() {
78 T::from_power_of_2_digits_asc(log_base, digits)
79 } else {
80 let mut digits = digits.collect_vec();
81 digits.reverse();
82 T::from_digits_desc(base, digits.into_iter())
83 }
84}
85
86fn from_digits_desc<
87 T: Digits<U> + TryFrom<U> + PrimitiveUnsigned + PowerOf2Digits<U>,
88 U: PrimitiveUnsigned,
89 I: Iterator<Item = U>,
90>(
91 base: &U,
92 digits: I,
93) -> Option<T> {
94 assert!(*base > U::ONE);
95 if let Some(log_base) = base.checked_log_base_2() {
96 T::from_power_of_2_digits_desc(log_base, digits)
97 } else {
98 let base = T::try_from(*base).ok()?;
99 let mut x = T::ZERO;
100 for digit in digits {
101 let digit = T::try_from(digit).ok()?;
102 if digit >= base {
103 return None;
104 }
105 x = x.checked_mul(base)?.checked_add(digit)?;
106 }
107 Some(x)
108 }
109}
110
111macro_rules! impl_digits {
112 ($t:ident) => {
113 macro_rules! impl_digits_inner {
114 ($u:ident) => {
115 impl Digits<$u> for $t {
116 /// Returns a [`Vec`] containing the digits of a number in ascending order
117 /// (least- to most-significant).
118 ///
119 /// The base must be convertible to `Self`. If `self` is 0, the [`Vec`] is
120 /// empty; otherwise, it ends with a nonzero digit.
121 ///
122 /// $f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or
123 /// $d_{k-1} \neq 0$, and
124 ///
125 /// $$
126 /// \sum_{i=0}^{k-1}b^i d_i = x.
127 /// $$
128 ///
129 /// # Worst-case complexity
130 /// $T(n) = O(n)$
131 ///
132 /// $M(n) = O(n)$
133 ///
134 /// where $T$ is time, $M$ is additional memory, and $n$ is
135 /// `self.significant_bits()`.
136 ///
137 /// # Panics
138 /// Panics if `base` is less than 2 or greater than `Self::MAX`.
139 ///
140 /// # Examples
141 /// See [here](super::general_digits#to_digits_asc).
142 #[inline]
143 fn to_digits_asc(&self, base: &$u) -> Vec<$u> {
144 to_digits_asc(self, base)
145 }
146
147 /// Returns a [`Vec`] containing the digits of a number in descending order
148 /// (most- to least-significant).
149 ///
150 /// The base must be convertible to `Self`. If `self` is 0, the [`Vec`] is
151 /// empty; otherwise, it begins with a nonzero digit.
152 ///
153 /// $f(x, b) = (d_i)_ {i=0}^{k-1}$, where $0 \leq d_i < b$ for all $i$, $k=0$ or
154 /// $d_{k-1} \neq 0$, and
155 ///
156 /// $$
157 /// \sum_{i=0}^{k-1}b^i d_{k-i-1} = x.
158 /// $$
159 ///
160 /// # Worst-case complexity
161 /// $T(n) = O(n)$
162 ///
163 /// $M(n) = O(n)$
164 ///
165 /// where $T$ is time, $M$ is additional memory, and $n$ is
166 /// `self.significant_bits()`.
167 ///
168 /// # Panics
169 /// Panics if `base` is less than 2 or greater than `$t::MAX`.
170 ///
171 /// # Examples
172 /// See [here](super::general_digits#to_digits_desc).
173 #[inline]
174 fn to_digits_desc(&self, base: &$u) -> Vec<$u> {
175 to_digits_desc(self, base)
176 }
177
178 /// Converts an iterator of digits into a value.
179 ///
180 /// The input digits are in ascending order (least- to most-significant). The
181 /// base must be no larger than `Self::MAX`. The function returns `None` if the
182 /// input represents a number that can't fit in `Self`, if `base` is greater
183 /// than `Self::MAX`, or if any of the digits are greater than or equal to the
184 /// base.
185 ///
186 /// $$
187 /// f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^id_i.
188 /// $$
189 ///
190 /// # Worst-case complexity
191 /// $T(n) = O(n)$
192 ///
193 /// $M(n) = O(1)$
194 ///
195 /// where $T$ is time, $M$ is additional memory, and $n$ is `digits.count()`.
196 ///
197 /// # Panics
198 /// Panics if `base` is less than 2.
199 ///
200 /// # Examples
201 /// See [here](super::general_digits#from_digits_asc).
202 #[inline]
203 fn from_digits_asc<I: Iterator<Item = $u>>(base: &$u, digits: I) -> Option<$t> {
204 from_digits_asc(base, digits)
205 }
206
207 /// Converts an iterator of digits into a value.
208 ///
209 /// The input digits are in descending order (most- to least-significant). The
210 /// base must be no larger than `Self::MAX`. The function returns `None` if the
211 /// input represents a number that can't fit in `Self`, if `base` is greater
212 /// than `Self::MAX`, or if any of the digits are greater than or equal to the
213 /// base.
214 ///
215 /// $$
216 /// f((d_i)_ {i=0}^{k-1}, b) = \sum_{i=0}^{k-1}b^{k-i-1}d_i.
217 /// $$
218 ///
219 /// # Worst-case complexity
220 /// $T(n) = O(n)$
221 ///
222 /// $M(n) = O(1)$
223 ///
224 /// where $T$ is time, $M$ is additional memory, and $n$ is `digits.count()`.
225 ///
226 /// # Panics
227 /// Panics if `base` is less than 2.
228 ///
229 /// # Examples
230 /// See [here](super::general_digits#from_digits_desc).
231 #[inline]
232 fn from_digits_desc<I: Iterator<Item = $u>>(
233 base: &$u,
234 digits: I,
235 ) -> Option<$t> {
236 from_digits_desc(base, digits)
237 }
238 }
239 };
240 }
241 apply_to_unsigneds!(impl_digits_inner);
242 };
243}
244apply_to_unsigneds!(impl_digits);