Trait RootRem 

pub trait RootRem<POW> {
    type RootOutput;
    type RemOutput;

    // Required method
    fn root_rem(self, exp: POW) -> (Self::RootOutput, Self::RemOutput);
}

Finds the floor of the $n$th root of a number, returning both the root and the remainder.

Required Associated Types

type RootOutput

type RemOutput

Required Methods

fn root_rem(self, exp: POW) -> (Self::RootOutput, Self::RemOutput)

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl RootRem<u64> for u8

fn root_rem(self, exp: u64) -> (Self, Self)

Returns the floor of the $n$th root of a u8, and the remainder (the difference between the u8 and the $n$th power of the floor).

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if exp is zero.

Examples

See here.

Notes

The u8 implementation uses lookup tables.

type RootOutput = u8

type RemOutput = u8

impl RootRem<u64> for u16

fn root_rem(self, exp: u64) -> (Self, Self)

Returns the floor of the $n$th root of a u16, and the remainder (the difference between the u16 and the $n$th power of the floor).

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if exp is zero.

Examples

See here.

Notes

The u16 implementation calls the implementation for u32s.

type RootOutput = u16

type RemOutput = u16

impl RootRem<u64> for u32

fn root_rem(self, exp: u64) -> (Self, Self)

Returns the floor of the $n$th root of a u32, and the remainder (the difference between the u32 and the $n$th power of the floor).

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if exp is zero.

Examples

See here.

Notes

For cube roots, the u32 implementation uses a piecewise Chebyshev approximation. For other roots, it uses Newton’s method. In both implementations, the result of these approximations is adjusted afterwards to account for error.

type RootOutput = u32

type RemOutput = u32

impl RootRem<u64> for u64

fn root_rem(self, exp: Self) -> (Self, Self)

Returns the floor of the $n$th root of a u64, and the remainder (the difference between the u64 and the $n$th power of the floor).

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if exp is zero.

Examples

See here.

Notes

For cube roots, the u64 implementation uses a piecewise Chebyshev approximation. For other roots, it uses Newton’s method. In both implementations, the result of these approximations is adjusted afterwards to account for error.

type RootOutput = u64

type RemOutput = u64

impl RootRem<u64> for u128

fn root_rem(self, exp: u64) -> (Self, Self)

Returns the floor of the $n$th root of a u128, and the remainder (the difference between the u128 and the $n$th power of the floor).

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

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(): constant for widths up to 64 bits and for exponents greater than 2, where a floating-point approximation is refined with $O(1)$ adjustments; 128-bit square roots (exp == 2) fall back to an $O(n)$ binary search.

Panics

Panics if exp is zero.

Examples

See here.

Notes

The u128 implementation computes the root using floating-point arithmetic. The approximate result is adjusted afterwards to account for error.

type RootOutput = u128

type RemOutput = u128

impl RootRem<u64> for usize

fn root_rem(self, exp: u64) -> (Self, Self)

Returns the floor of the $n$th root of a usize, and the remainder (the difference between the usize and the $n$th power of the floor).

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

Worst-case complexity

Constant time and additional memory.

Panics

Panics if exp is zero.

Examples

See here.

Notes

The usize implementation calls the u32 or u64 implementations.

type RootOutput = usize

type RemOutput = usize

Implementors