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
Dyn Compatibility§
This trait is dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".
Implementations on Foreign Types§
Source§impl FloorSqrt for u128
impl FloorSqrt for u128
Source§fn floor_sqrt(self) -> Self
fn floor_sqrt(self) -> Self
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}$.