Trait malachite_base::num::arithmetic::traits::SqrtRem

source · [−]
pub trait SqrtRem {
    type SqrtOutput;
    type RemOutput;

    fn sqrt_rem(self) -> (Self::SqrtOutput, Self::RemOutput);
}
Expand description

Finds the floor of the square root of a number, returning both the root and the remainder.

Required Associated Types

Required Methods

Implementations on Foreign Types

Returns the floor of the square root of a u8, and the remainder (the difference between the u8 and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The u8 implementation uses a lookup table.

Returns the floor of the square root of an integer, and the remainder (the difference between the integer and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

For u32 and u64, the square root is computed using Newton’s method.

Returns the floor of the square root of an integer, and the remainder (the difference between the integer and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

For u32 and u64, the square root is computed using Newton’s method.

Returns the floor of the square root of a u16, and the remainder (the difference between the u16 and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The u16 implementation calls the implementation for u32s.

Returns the floor of the square root of a usize, and the remainder (the difference between the usize and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The usize implementation calls the u32 or u64 implementations.

Returns the floor of the square root of a u128, and the remainder (the difference between the u128 and the square of the floor).

$f(x) = (\lfloor\sqrt{x}\rfloor, x - \lfloor\sqrt{x}\rfloor^2)$.

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}$.

Implementors