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 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
use conversion::traits::ContinuedFraction;
use malachite_base::num::arithmetic::traits::{DivMod, Floor};
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::mem::swap;
use Rational;
/// An iterator that produces the continued fraction of a [`Rational`].
///
/// See [`continued_fraction`](Rational::continued_fraction) for more information.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct RationalContinuedFraction {
numerator: Natural,
denominator: Natural,
}
impl RationalContinuedFraction {
pub_crate_test! {is_done(&self) -> bool {
self.denominator == 0u32 || self.numerator == 0u32
}}
}
impl Iterator for RationalContinuedFraction {
type Item = Natural;
fn next(&mut self) -> Option<Natural> {
if self.denominator == 0u32 || self.numerator == 0u32 {
None
} else {
let n;
(n, self.numerator) = (&self.numerator).div_mod(&self.denominator);
swap(&mut self.numerator, &mut self.denominator);
Some(n)
}
}
}
impl ContinuedFraction for Rational {
type CF = RationalContinuedFraction;
/// Returns the continued fraction of a [`Rational`], taking the [`Rational`] by value.
///
/// The output has two components. The first is the first value of the continued fraction,
/// which may be any [`Integer`](malachite_nz::integer::Integer) and is equal to the floor of
/// the [`Rational`]. The second is an iterator that produces the remaining values, which are
/// all positive. Using the standard notation for continued fractions, the first value is the
/// number before the semicolon, and the second value produces the remaining numbers.
///
/// Each rational number has two continued fraction representations. The shorter of the two
/// representations (the one that does not end in 1) is returned.
///
/// $f(x) = (a_0, (a_1, a_2, \ldots, a_3)),$ where $x = [a_0; a_1, a_2, \ldots, a_3]$ and
/// $a_3 \neq 1$.
///
/// The output length is $O(n)$, where $n$ is `self.significant_bits()`.
///
/// # Worst-case complexity per iteration
/// $T(n) = O(n \log n \log\log n)$
///
/// $M(n) = O(n \log n)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
///
/// # Examples
/// ```
/// extern crate itertools;
/// extern crate malachite_base;
///
/// use itertools::Itertools;
/// use malachite_base::strings::ToDebugString;
/// use malachite_q::conversion::traits::ContinuedFraction;
/// use malachite_q::Rational;
///
/// let (head, tail) = Rational::from_signeds(2, 3).continued_fraction();
/// let tail = tail.collect_vec();
/// assert_eq!(head, 0);
/// assert_eq!(tail.to_debug_string(), "[1, 2]");
///
/// let (head, tail) = Rational::from_signeds(355, 113).continued_fraction();
/// let tail = tail.collect_vec();
/// assert_eq!(head, 3);
/// assert_eq!(tail.to_debug_string(), "[7, 16]");
/// ```
fn continued_fraction(mut self) -> (Integer, RationalContinuedFraction) {
let f = (&self).floor();
self -= Rational::from(&f);
let (d, n) = self.into_numerator_and_denominator();
(
f,
RationalContinuedFraction {
numerator: n,
denominator: d,
},
)
}
}
impl<'a> ContinuedFraction for &'a Rational {
type CF = RationalContinuedFraction;
/// Returns the continued fraction of a [`Rational`], taking the [`Rational`] by reference.
///
/// The output has two components. The first is the first value of the continued fraction,
/// which may be any [`Integer`](malachite_nz::integer::Integer) and is equal to the floor of
/// the [`Rational`]. The second is an iterator that produces the remaining values, which are
/// all positive. Using the standard notation for continued fractions, the first value is the
/// number before the semicolon, and the second value produces the remaining numbers.
///
/// Each rational number has two continued fraction representations. The shorter of the two
/// representations (the one that does not end in 1) is returned.
///
/// $f(x) = (a_0, (a_1, a_2, \ldots, a_3)),$ where $x = [a_0; a_1, a_2, \ldots, a_3]$ and
/// $a_3 \neq 1$.
///
/// The output length is $O(n)$, where $n$ is `self.significant_bits()`.
///
/// # Worst-case complexity per iteration
/// $T(n) = O(n \log n \log\log n)$
///
/// $M(n) = O(n \log n)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
///
/// # Examples
/// ```
/// extern crate itertools;
/// extern crate malachite_base;
///
/// use itertools::Itertools;
/// use malachite_base::strings::ToDebugString;
/// use malachite_q::conversion::traits::ContinuedFraction;
/// use malachite_q::Rational;
///
/// let (head, tail) = (&Rational::from_signeds(2, 3)).continued_fraction();
/// let tail = tail.collect_vec();
/// assert_eq!(head, 0);
/// assert_eq!(tail.to_debug_string(), "[1, 2]");
///
/// let (head, tail) = (&Rational::from_signeds(355, 113)).continued_fraction();
/// let tail = tail.collect_vec();
/// assert_eq!(head, 3);
/// assert_eq!(tail.to_debug_string(), "[7, 16]");
/// ```
fn continued_fraction(self) -> (Integer, RationalContinuedFraction) {
let f = self.floor();
let (d, n) = (self - Rational::from(&f)).into_numerator_and_denominator();
(
f,
RationalContinuedFraction {
numerator: n,
denominator: d,
},
)
}
}