Trait malachite_base::num::arithmetic::traits::FloorSqrt
source · pub trait FloorSqrt {
type Output;
// Required method
fn floor_sqrt(self) -> Self::Output;
}Expand description
Finds the floor of the square root of a number.
Required Associated Types§
Required Methods§
fn floor_sqrt(self) -> Self::Output
Implementations on Foreign Types§
source§impl FloorSqrt for u128
impl FloorSqrt for u128
source§fn floor_sqrt(self) -> u128
fn floor_sqrt(self) -> u128
Returns the floor of the square root of a u128.
$f(x) = \lfloor\sqrt{x}\rfloor$.
§Worst-case complexity
$T(n) = O(n)$
$M(n) = O(1)$
where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().
§Examples
See here.
§Notes
For u128, using a floating-point approximation and refining the result works, but the
number of necessary adjustments becomes large for large u128s. To overcome this, large
u128s switch to a binary search algorithm. To get decent starting bounds, the following
fact is used:
If $x$ is nonzero and has $b$ significant bits, then
$2^{b-1} \leq x \leq 2^b-1$,
$2^{b-1} \leq x \leq 2^b$,
$2^{2\lfloor (b-1)/2 \rfloor} \leq x \leq 2^{2\lceil b/2 \rceil}$,
$2^{2(\lceil b/2 \rceil-1)} \leq x \leq 2^{2\lceil b/2 \rceil}$,
$\lfloor\sqrt{2^{2(\lceil b/2 \rceil-1)}}\rfloor \leq \lfloor\sqrt{x}\rfloor \leq \lfloor\sqrt{2^{2\lceil b/2 \rceil}}\rfloor$, since $x \mapsto \lfloor\sqrt{x}\rfloor$ is weakly increasing,
$2^{\lceil b/2 \rceil-1} \leq \lfloor\sqrt{x}\rfloor \leq 2^{\lceil b/2 \rceil}$.
For example, since $10^9$ has 30 significant bits, we know that $2^{14} \leq \lfloor\sqrt{10^9}\rfloor \leq 2^{15}$.