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
use malachite_base::num::arithmetic::traits::{AddMulAssign, UnsignedAbs};
use malachite_base::num::basic::traits::{One, Zero};
use malachite_nz::integer::Integer;
use malachite_nz::natural::Natural;
use std::mem::swap;
use Rational;
impl Rational {
/// Converts a finite continued fraction to a [`Rational`], taking the inputs by value.
///
/// The input 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 of the remaining values, which must all be
/// positive. Using the standard notation for continued fractions, the first value is the
/// number before the semicolon, and the second value contains the remaining numbers.
///
/// Each rational number has two continued fraction representations. Either one is a valid
/// input.
///
/// $f(a_0, (a_1, a_2, a_3, \ldots)) = [a_0; a_1, a_2, a_3, \ldots]$.
///
/// # Worst-case complexity
/// $T(n, m) = O((nm)^2 \log (nm) \log\log (nm))$
///
/// $M(n, m) = O(nm \log (nm))$
///
/// where $T$ is time, $M$ is additional memory, $n$ is
/// `max(floor.significant_bits(), xs.map(Natural::significant_bits).max())`, and $m$ is
/// `xs.count()`.
///
/// # Panics
/// Panics if any [`Natural`](malachite_nz::natural::Natural) in `xs` is zero.
///
/// # Examples
/// ```
/// extern crate malachite_base;
/// extern crate malachite_nz;
///
/// use malachite_base::num::basic::traits::Zero;
/// use malachite_base::vecs::vec_from_str;
/// use malachite_nz::integer::Integer;
/// use malachite_q::Rational;
///
/// let xs = vec_from_str("[1, 2]").unwrap().into_iter();
/// assert_eq!(Rational::from_continued_fraction(Integer::ZERO, xs).to_string(), "2/3");
///
/// let xs = vec_from_str("[7, 16]").unwrap().into_iter();
/// assert_eq!(Rational::from_continued_fraction(Integer::from(3), xs).to_string(), "355/113");
/// ```
pub fn from_continued_fraction<I: Iterator<Item = Natural>>(floor: Integer, xs: I) -> Rational {
let mut previous_numerator = Integer::ONE;
let mut previous_denominator = Natural::ZERO;
let mut numerator = floor;
let mut denominator = Natural::ONE;
for n in xs {
assert_ne!(n, 0u32);
previous_numerator.add_mul_assign(&numerator, Integer::from(&n));
previous_denominator.add_mul_assign(&denominator, n);
swap(&mut numerator, &mut previous_numerator);
swap(&mut denominator, &mut previous_denominator);
}
Rational {
sign: numerator >= 0,
numerator: numerator.unsigned_abs(),
denominator,
}
}
/// Converts a finite continued fraction to a [`Rational`], taking the inputs by reference.
///
/// The input 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 of the remaining values, which must all be
/// positive. Using the standard notation for continued fractions, the first value is the
/// number before the semicolon, and the second value contains the remaining numbers.
///
/// Each rational number has two continued fraction representations. Either one is a valid
/// input.
///
/// $f(a_0, (a_1, a_2, a_3, \ldots)) = [a_0; a_1, a_2, a_3, \ldots]$.
///
/// # Worst-case complexity
/// $T(n, m) = O((nm)^2 \log (nm) \log\log (nm))$
///
/// $M(n, m) = O(nm \log (nm))$
///
/// where $T$ is time, $M$ is additional memory, $n$ is
/// `max(floor.significant_bits(), xs.map(Natural::significant_bits).max())`, and $m$ is
/// `xs.count()`.
///
/// # Panics
/// Panics if any [`Natural`](malachite_nz::natural::Natural) in `xs` is zero.
///
/// # Examples
/// ```
/// extern crate malachite_base;
/// extern crate malachite_nz;
///
/// use malachite_base::num::basic::traits::Zero;
/// use malachite_base::vecs::vec_from_str;
/// use malachite_nz::integer::Integer;
/// use malachite_q::Rational;
///
/// let xs = vec_from_str("[1, 2]").unwrap();
/// assert_eq!(
/// Rational::from_continued_fraction_ref(&Integer::ZERO, xs.iter()).to_string(),
/// "2/3"
/// );
///
/// let xs = vec_from_str("[7, 16]").unwrap();
/// assert_eq!(
/// Rational::from_continued_fraction_ref(&Integer::from(3), xs.iter()).to_string(),
/// "355/113"
/// );
/// ```
pub fn from_continued_fraction_ref<'a, I: Iterator<Item = &'a Natural>>(
floor: &Integer,
xs: I,
) -> Rational {
let mut previous_numerator = Integer::ONE;
let mut previous_denominator = Natural::ZERO;
let mut numerator = floor.clone();
let mut denominator = Natural::ONE;
for n in xs {
assert_ne!(*n, 0u32);
previous_numerator.add_mul_assign(&numerator, Integer::from(n));
previous_denominator.add_mul_assign(&denominator, n);
swap(&mut numerator, &mut previous_numerator);
swap(&mut denominator, &mut previous_denominator);
}
Rational {
sign: numerator >= 0,
numerator: numerator.unsigned_abs(),
denominator,
}
}
}