Trait malachite_base::num::arithmetic::traits::CeilingSqrt
source · pub trait CeilingSqrt {
type Output;
fn ceiling_sqrt(self) -> Self::Output;
}
Expand description
Finds the ceiling of the square root of a number.
Required Associated Types§
Required Methods§
fn ceiling_sqrt(self) -> Self::Output
Implementations on Foreign Types§
source§impl CeilingSqrt for u8
impl CeilingSqrt for u8
source§impl CeilingSqrt for u32
impl CeilingSqrt for u32
source§impl CeilingSqrt for u64
impl CeilingSqrt for u64
source§impl CeilingSqrt for u16
impl CeilingSqrt for u16
source§impl CeilingSqrt for usize
impl CeilingSqrt for usize
source§impl CeilingSqrt for u128
impl CeilingSqrt for u128
source§fn ceiling_sqrt(self) -> u128
fn ceiling_sqrt(self) -> u128
Returns the ceiling of the square root of a u128
.
$f(x) = \lceil\sqrt{x}\rceil$.
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 u128
s. To overcome this, large
u128
s 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}$.