Trait malachite_base::num::arithmetic::traits::RootRem

source · [−]

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

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

Expand description

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

Required Associated Types

source

Required Methods

source

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

Implementations on Foreign Types

source

impl RootRem<u64> for u8

source

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

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

Notes

The u8 implementation uses lookup tables.

impl RootRem<u64> for u16

source

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

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

Notes

The u16 implementation calls the implementation for u32s.

impl RootRem<u64> for u32

source

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

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

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

source

impl RootRem<u64> for u64

source

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

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.