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
sourceimpl CeilingSqrt for u8
impl CeilingSqrt for u8
sourceimpl CeilingSqrt for u32
impl CeilingSqrt for u32
sourceimpl CeilingSqrt for u64
impl CeilingSqrt for u64
sourceimpl CeilingSqrt for u16
impl CeilingSqrt for u16
sourceimpl CeilingSqrt for usize
impl CeilingSqrt for usize
sourceimpl CeilingSqrt for u128
impl CeilingSqrt for u128
sourcefn 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}$.
type Output = u128
sourceimpl CeilingSqrt for i8
impl CeilingSqrt for i8
sourcefn ceiling_sqrt(self) -> i8
fn ceiling_sqrt(self) -> i8
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.
type Output = i8
sourceimpl CeilingSqrt for i16
impl CeilingSqrt for i16
sourcefn ceiling_sqrt(self) -> i16
fn ceiling_sqrt(self) -> i16
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.
type Output = i16
sourceimpl CeilingSqrt for i32
impl CeilingSqrt for i32
sourcefn ceiling_sqrt(self) -> i32
fn ceiling_sqrt(self) -> i32
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.
type Output = i32
sourceimpl CeilingSqrt for i64
impl CeilingSqrt for i64
sourcefn ceiling_sqrt(self) -> i64
fn ceiling_sqrt(self) -> i64
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.
type Output = i64
sourceimpl CeilingSqrt for i128
impl CeilingSqrt for i128
sourcefn ceiling_sqrt(self) -> i128
fn ceiling_sqrt(self) -> i128
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.
type Output = i128
sourceimpl CeilingSqrt for isize
impl CeilingSqrt for isize
sourcefn ceiling_sqrt(self) -> isize
fn ceiling_sqrt(self) -> isize
Returns the ceiling of the square root of an integer.
$f(x) = \lceil\sqrt{x}\rceil$.
Worst-case complexity
Constant time and additional memory.
Panics
Panics if self
is negative.
Examples
See here.