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
// 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 malachite_base::num::arithmetic::traits::{CheckedSqrt, UnsignedAbs};
use malachite_base::num::logic::traits::SignificantBits;
use malachite_nz::integer::Integer;
impl CheckedSqrt for Rational {
type Output = Rational;
/// Returns the the square root of a [`Rational`], or `None` if it is not a perfect square. The
/// [`Rational`] is taken by value.
///
/// $$
/// f(x) = \\begin{cases}
/// \operatorname{Some}(sqrt{x}) & \text{if} \\quad \sqrt{x} \in \mathbb{Q}, \\\\
/// \operatorname{None} & \textrm{otherwise}.
/// \\end{cases}
/// $$
///
/// # Worst-case complexity
/// $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()`.
///
/// # Panics
/// Panics if `self` is negative.
///
/// # Examples
/// ```
/// use malachite_base::num::arithmetic::traits::CheckedSqrt;
/// use malachite_base::strings::ToDebugString;
/// use malachite_q::Rational;
///
/// assert_eq!(Rational::from(99u8).checked_sqrt().to_debug_string(), "None");
/// assert_eq!(Rational::from(100u8).checked_sqrt().to_debug_string(), "Some(10)");
/// assert_eq!(Rational::from(101u8).checked_sqrt().to_debug_string(), "None");
/// assert_eq!(Rational::from_signeds(22, 7).checked_sqrt().to_debug_string(), "None");
/// assert_eq!(Rational::from_signeds(25, 9).checked_sqrt().to_debug_string(), "Some(5/3)");
/// ```
fn checked_sqrt(self) -> Option<Rational> {
let sign = self >= 0;
let (n, d) = self.into_numerator_and_denominator();
let sqrt_n;
let sqrt_d;
if n.significant_bits() <= d.significant_bits() {
sqrt_n = Integer::from_sign_and_abs(sign, n).checked_sqrt()?;
sqrt_d = d.checked_sqrt()?;
} else {
sqrt_d = d.checked_sqrt()?;
sqrt_n = Integer::from_sign_and_abs(sign, n).checked_sqrt()?;
}
Some(Rational {
sign: sqrt_n >= 0,
numerator: sqrt_n.unsigned_abs(),
denominator: sqrt_d,
})
}
}
impl<'a> CheckedSqrt for &'a Rational {
type Output = Rational;
/// Returns the the square root of a [`Rational`], or `None` if it is not a perfect square. The
/// [`Rational`] is taken by reference.
///
/// $$
/// f(x) = \\begin{cases}
/// \operatorname{Some}(sqrt{x}) & \text{if} \\quad \sqrt{x} \in \mathbb{Q}, \\\\
/// \operatorname{None} & \textrm{otherwise}.
/// \\end{cases}
/// $$
///
/// # Worst-case complexity
/// $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()`.
///
/// # Panics
/// Panics if `self` is negative.
///
/// # Examples
/// ```
/// use malachite_base::num::arithmetic::traits::CheckedSqrt;
/// use malachite_base::strings::ToDebugString;
/// use malachite_q::Rational;
///
/// assert_eq!((&Rational::from(99u8)).checked_sqrt().to_debug_string(), "None");
/// assert_eq!((&Rational::from(100u8)).checked_sqrt().to_debug_string(), "Some(10)");
/// assert_eq!((&Rational::from(101u8)).checked_sqrt().to_debug_string(), "None");
/// assert_eq!((&Rational::from_signeds(22, 7)).checked_sqrt().to_debug_string(), "None");
/// assert_eq!((&Rational::from_signeds(25, 9)).checked_sqrt().to_debug_string(), "Some(5/3)");
/// ```
fn checked_sqrt(self) -> Option<Rational> {
let (n, d) = self.numerator_and_denominator_ref();
let sqrt_n;
let sqrt_d;
if n.significant_bits() <= d.significant_bits() {
sqrt_n = Integer::from_sign_and_abs_ref(*self >= 0, n).checked_sqrt()?;
sqrt_d = d.checked_sqrt()?;
} else {
sqrt_d = d.checked_sqrt()?;
sqrt_n = Integer::from_sign_and_abs_ref(*self >= 0, n).checked_sqrt()?;
}
Some(Rational {
sign: sqrt_n >= 0,
numerator: sqrt_n.unsigned_abs(),
denominator: sqrt_d,
})
}
}