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::Rational;
use core::mem::swap;
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;
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`] 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`] in `xs` is zero.
///
/// # Examples
/// ```
/// 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`] 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`] in `xs` is zero.
///
/// # Examples
/// ```
/// 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,
}
}
}