Trait DivModPrecomputed 

pub trait DivModPrecomputed<RHS = Self> {
    type DivOutput;
    type ModOutput;
    type Data;

    // Required methods
    fn precompute_div_mod_data(other: &RHS) -> Self::Data;
    fn div_mod_precomputed(
        self,
        other: RHS,
        data: &Self::Data,
    ) -> (Self::DivOutput, Self::ModOutput);
}

Divides two numbers, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the divisor (second input).

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

If multiple divisions by the same divisor are necessary, it can be quicker to precompute some piece of data based on the divisor and reuse it in the division calls. This trait provides a function for precomputing the data and a function for using it during division.

Required Associated Types

type DivOutput

type ModOutput

type Data

Required Methods

fn precompute_div_mod_data(other: &RHS) -> Self::Data

Precomputes some data to use for division.

fn div_mod_precomputed( self, other: RHS, data: &Self::Data, ) -> (Self::DivOutput, Self::ModOutput)

Dyn Compatibility

This trait is not dyn compatible.

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

Implementations on Foreign Types

impl DivModPrecomputed for i8

fn precompute_div_mod_data(other: &i8) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: i8, data: &Self::Data) -> (i8, i8)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = i8

type ModOutput = i8

type Data = <u8 as DivModPrecomputed>::Data

impl DivModPrecomputed for i16

fn precompute_div_mod_data(other: &i16) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: i16, data: &Self::Data) -> (i16, i16)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = i16

type ModOutput = i16

type Data = <u16 as DivModPrecomputed>::Data

impl DivModPrecomputed for i32

fn precompute_div_mod_data(other: &i32) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: i32, data: &Self::Data) -> (i32, i32)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = i32

type ModOutput = i32

type Data = <u32 as DivModPrecomputed>::Data

impl DivModPrecomputed for i64

fn precompute_div_mod_data(other: &i64) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: i64, data: &Self::Data) -> (i64, i64)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = i64

type ModOutput = i64

type Data = <u64 as DivModPrecomputed>::Data

impl DivModPrecomputed for i128

fn precompute_div_mod_data(other: &i128) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: i128, data: &Self::Data) -> (i128, i128)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = i128

type ModOutput = i128

type Data = <u128 as DivModPrecomputed>::Data

impl DivModPrecomputed for isize

fn precompute_div_mod_data(other: &isize) -> Self::Data

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

The data depends only on the absolute value of the divisor.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: isize, data: &Self::Data) -> (isize, isize)

Divides a number by another number, returning the quotient and remainder. The quotient is rounded towards negative infinity, and the remainder has the same sign as the second number.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is $t::MIN and other is -1.

Examples

See here.

type DivOutput = isize

type ModOutput = isize

type Data = <usize as DivModPrecomputed>::Data

impl DivModPrecomputed for u8

fn precompute_div_mod_data(other: &u8) -> (u32, u64)

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn div_mod_precomputed(self, other: u8, data: &(u32, u64)) -> (u8, u8)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

type DivOutput = u8

type ModOutput = u8

type Data = (u32, u64)

impl DivModPrecomputed for u16

fn precompute_div_mod_data(other: &u16) -> (u32, u64)

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn div_mod_precomputed(self, other: u16, data: &(u32, u64)) -> (u16, u16)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

type DivOutput = u16

type ModOutput = u16

type Data = (u32, u64)

impl DivModPrecomputed for u32

fn precompute_div_mod_data(other: &u32) -> (u32, u64)

Precomputes data for division: the limbs_invert_limb-style inverse of the normalized divisor, and the normalizing shift. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1, with the normalizing shift retained, as in FLINT’s nmod_t.

fn div_mod_precomputed(self, other: u32, data: &(u32, u64)) -> (u32, u32)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

This trades the hardware division for a widening multiplication and adjustments, which pays off on processors whose dividers are slow relative to their multipliers; on processors with fast, pipelined dividers, plain division may be faster.

Examples

See here.

This is equivalent to udiv_qrnnd_preinv from gmp-impl.h, GMP 6.2.1, where the dividend occupies a single limb.

type DivOutput = u32

type ModOutput = u32

type Data = (u32, u64)

impl DivModPrecomputed for u64

fn precompute_div_mod_data(other: &u64) -> (u64, u64)

Precomputes data for division: the limbs_invert_limb-style inverse of the normalized divisor, and the normalizing shift. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1, with the normalizing shift retained, as in FLINT’s nmod_t.

fn div_mod_precomputed(self, other: u64, data: &(u64, u64)) -> (u64, u64)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

This trades the hardware division for a widening multiplication and adjustments, which pays off on processors whose dividers are slow relative to their multipliers; on processors with fast, pipelined dividers, plain division may be faster.

Examples

See here.

This is equivalent to udiv_qrnnd_preinv from gmp-impl.h, GMP 6.2.1, where the dividend occupies a single limb.

type DivOutput = u64

type ModOutput = u64

type Data = (u64, u64)

impl DivModPrecomputed for u128

fn precompute_div_mod_data(other: &Self)

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

fn div_mod_precomputed(self, other: Self, _data: &()) -> (Self, Self)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

Examples

See here.

type DivOutput = u128

type ModOutput = u128

type Data = ()

impl DivModPrecomputed for usize

fn precompute_div_mod_data(other: &Self) -> (Self, u64)

Precomputes data for division. See div_mod_precomputed and div_assign_mod_precomputed.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if other is 0.

This is equivalent to n_preinvert_limb from ulong_extras.h, FLINT 2.7.1.

fn div_mod_precomputed(self, other: Self, data: &(Self, u64)) -> (Self, Self)

Divides a number by another number, returning the quotient and remainder.

The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < y$.

Some precomputed data is provided; this speeds up computations involving several divisions by the same divisor. The precomputed data should be obtained using precompute_div_mod_data.

Worst-case complexity

Constant time and additional memory.

Examples

See here.

type DivOutput = usize

type ModOutput = usize

type Data = (usize, u64)

Implementors