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

pub trait SqrtRem {
    type SqrtOutput;
    type RemOutput;

    // Required method
    fn sqrt_rem(self) -> (Self::SqrtOutput, Self::RemOutput);
}

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

Required Associated Types

type SqrtOutput

type RemOutput

Required Methods

fn sqrt_rem(self) -> (Self::SqrtOutput, Self::RemOutput)

Implementations on Foreign Types

impl SqrtRem for u8

fn sqrt_rem(self) -> (u8, u8)

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.

type SqrtOutput = u8

type RemOutput = u8

impl SqrtRem for u16

fn sqrt_rem(self) -> (u16, u16)

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.

type SqrtOutput = u16

type RemOutput = u16

impl SqrtRem for u32

fn sqrt_rem(self) -> (u32, u32)

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.

type SqrtOutput = u32

type RemOutput = u32

impl SqrtRem for u64

fn sqrt_rem(self) -> (u64, u64)

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.

type SqrtOutput = u64

type RemOutput = u64

impl SqrtRem for u128

fn sqrt_rem(self) -> (u128, u128)

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

type SqrtOutput = u128

type RemOutput = u128

impl SqrtRem for usize

fn sqrt_rem(self) -> (usize, usize)

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.

type SqrtOutput = usize

type RemOutput = usize

Implementors