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