malachite_q/arithmetic/
sqrt.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::Rational;
10use malachite_base::num::arithmetic::traits::{CheckedSqrt, UnsignedAbs};
11use malachite_base::num::logic::traits::SignificantBits;
12use malachite_nz::integer::Integer;
13
14impl CheckedSqrt for Rational {
15    type Output = Self;
16
17    /// Returns the the square root of a [`Rational`], or `None` if it is not a perfect square. The
18    /// [`Rational`] is taken by value.
19    ///
20    /// $$
21    /// f(x) = \\begin{cases}
22    ///     \operatorname{Some}(sqrt{x}) & \text{if} \\quad \sqrt{x} \in \mathbb{Q}, \\\\
23    ///     \operatorname{None} & \textrm{otherwise}.
24    /// \\end{cases}
25    /// $$
26    ///
27    /// # Worst-case complexity
28    /// $T(n) = O(n \log n \log\log n)$
29    ///
30    /// $M(n) = O(n \log n)$
31    ///
32    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
33    ///
34    /// # Panics
35    /// Panics if `self` is negative.
36    ///
37    /// # Examples
38    /// ```
39    /// use malachite_base::num::arithmetic::traits::CheckedSqrt;
40    /// use malachite_base::strings::ToDebugString;
41    /// use malachite_q::Rational;
42    ///
43    /// assert_eq!(
44    ///     Rational::from(99u8).checked_sqrt().to_debug_string(),
45    ///     "None"
46    /// );
47    /// assert_eq!(
48    ///     Rational::from(100u8).checked_sqrt().to_debug_string(),
49    ///     "Some(10)"
50    /// );
51    /// assert_eq!(
52    ///     Rational::from(101u8).checked_sqrt().to_debug_string(),
53    ///     "None"
54    /// );
55    /// assert_eq!(
56    ///     Rational::from_signeds(22, 7)
57    ///         .checked_sqrt()
58    ///         .to_debug_string(),
59    ///     "None"
60    /// );
61    /// assert_eq!(
62    ///     Rational::from_signeds(25, 9)
63    ///         .checked_sqrt()
64    ///         .to_debug_string(),
65    ///     "Some(5/3)"
66    /// );
67    /// ```
68    fn checked_sqrt(self) -> Option<Self> {
69        assert!(self >= 0);
70        let (n, d) = self.into_numerator_and_denominator();
71        let sqrt_n;
72        let sqrt_d;
73        if n.significant_bits() <= d.significant_bits() {
74            sqrt_n = n.checked_sqrt()?;
75            sqrt_d = d.checked_sqrt()?;
76        } else {
77            sqrt_d = d.checked_sqrt()?;
78            sqrt_n = n.checked_sqrt()?;
79        }
80        Some(Self {
81            sign: sqrt_n >= 0,
82            numerator: sqrt_n,
83            denominator: sqrt_d,
84        })
85    }
86}
87
88impl CheckedSqrt for &Rational {
89    type Output = Rational;
90
91    /// Returns the the square root of a [`Rational`], or `None` if it is not a perfect square. The
92    /// [`Rational`] is taken by reference.
93    ///
94    /// $$
95    /// f(x) = \\begin{cases}
96    ///     \operatorname{Some}(sqrt{x}) & \text{if} \\quad \sqrt{x} \in \mathbb{Q}, \\\\
97    ///     \operatorname{None} & \textrm{otherwise}.
98    /// \\end{cases}
99    /// $$
100    ///
101    /// # Worst-case complexity
102    /// $T(n) = O(n \log n \log\log n)$
103    ///
104    /// $M(n) = O(n \log n)$
105    ///
106    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
107    ///
108    /// # Panics
109    /// Panics if `self` is negative.
110    ///
111    /// # Examples
112    /// ```
113    /// use malachite_base::num::arithmetic::traits::CheckedSqrt;
114    /// use malachite_base::strings::ToDebugString;
115    /// use malachite_q::Rational;
116    ///
117    /// assert_eq!(
118    ///     (&Rational::from(99u8)).checked_sqrt().to_debug_string(),
119    ///     "None"
120    /// );
121    /// assert_eq!(
122    ///     (&Rational::from(100u8)).checked_sqrt().to_debug_string(),
123    ///     "Some(10)"
124    /// );
125    /// assert_eq!(
126    ///     (&Rational::from(101u8)).checked_sqrt().to_debug_string(),
127    ///     "None"
128    /// );
129    /// assert_eq!(
130    ///     (&Rational::from_signeds(22, 7))
131    ///         .checked_sqrt()
132    ///         .to_debug_string(),
133    ///     "None"
134    /// );
135    /// assert_eq!(
136    ///     (&Rational::from_signeds(25, 9))
137    ///         .checked_sqrt()
138    ///         .to_debug_string(),
139    ///     "Some(5/3)"
140    /// );
141    /// ```
142    fn checked_sqrt(self) -> Option<Rational> {
143        let (n, d) = self.numerator_and_denominator_ref();
144        let sqrt_n;
145        let sqrt_d;
146        if n.significant_bits() <= d.significant_bits() {
147            sqrt_n = Integer::from_sign_and_abs_ref(*self >= 0, n).checked_sqrt()?;
148            sqrt_d = d.checked_sqrt()?;
149        } else {
150            sqrt_d = d.checked_sqrt()?;
151            sqrt_n = Integer::from_sign_and_abs_ref(*self >= 0, n).checked_sqrt()?;
152        }
153        Some(Rational {
154            sign: sqrt_n >= 0,
155            numerator: sqrt_n.unsigned_abs(),
156            denominator: sqrt_d,
157        })
158    }
159}
malachite_q/arithmetic/sqrt.rs

malachite_q/arithmetic/
sqrt.rs
