Struct Normalized3by2Divisor

pub struct Normalized3by2Divisor<T, D> { /* private fields */ }

Divide a 3-Word by a prearranged DoubleWord divisor.

Assumes quotient fits in a Word.

Möller, Granlund, “Improved division by invariant integers” Algorithm 5.

Implementations

impl Normalized3by2Divisor<u8, u16>

pub const fn invert_double_word(divisor: u16) -> u8

Calculate the inverse m > 0 of a normalized divisor (fit in a DoubleWord), such that

(m + B) * divisor = B^3 - k for some 1 <= k <= divisor

Möller, Granlund, “Improved division by invariant integers”, Algorithm 6.

pub const fn new(divisor: u16) -> Self

Initialize from a given normalized divisor.

divisor must have top bit of 1

pub const fn div_rem_2by2(&self, a: u16) -> (u16, u16)

pub const fn div_rem_3by2(&self, a_lo: u8, a_hi: u16) -> (u8, u16)

The input a is arranged as (lo, mi & hi) The output is (a / divisor, a % divisor)

pub const fn div_rem_4by2(&self, a_lo: u16, a_hi: u16) -> (u16, u16)

Divdide a 4-word number with double word divisor

The output is (a / divisor, a % divisor)

impl Normalized3by2Divisor<u16, u32>

pub const fn invert_double_word(divisor: u32) -> u16

Calculate the inverse m > 0 of a normalized divisor (fit in a DoubleWord), such that

(m + B) * divisor = B^3 - k for some 1 <= k <= divisor

Möller, Granlund, “Improved division by invariant integers”, Algorithm 6.

pub const fn new(divisor: u32) -> Self

Initialize from a given normalized divisor.

divisor must have top bit of 1

pub const fn div_rem_2by2(&self, a: u32) -> (u32, u32)

pub const fn div_rem_3by2(&self, a_lo: u16, a_hi: u32) -> (u16, u32)

The input a is arranged as (lo, mi & hi) The output is (a / divisor, a % divisor)

pub const fn div_rem_4by2(&self, a_lo: u32, a_hi: u32) -> (u32, u32)

Divdide a 4-word number with double word divisor

The output is (a / divisor, a % divisor)

impl Normalized3by2Divisor<u32, u64>

pub const fn invert_double_word(divisor: u64) -> u32

Calculate the inverse m > 0 of a normalized divisor (fit in a DoubleWord), such that

(m + B) * divisor = B^3 - k for some 1 <= k <= divisor

Möller, Granlund, “Improved division by invariant integers”, Algorithm 6.

pub const fn new(divisor: u64) -> Self

Initialize from a given normalized divisor.

divisor must have top bit of 1

pub const fn div_rem_2by2(&self, a: u64) -> (u64, u64)

pub const fn div_rem_3by2(&self, a_lo: u32, a_hi: u64) -> (u32, u64)

The input a is arranged as (lo, mi & hi) The output is (a / divisor, a % divisor)

pub const fn div_rem_4by2(&self, a_lo: u64, a_hi: u64) -> (u64, u64)

Divdide a 4-word number with double word divisor

The output is (a / divisor, a % divisor)

impl Normalized3by2Divisor<u64, u128>

pub const fn invert_double_word(divisor: u128) -> u64

Calculate the inverse m > 0 of a normalized divisor (fit in a DoubleWord), such that

(m + B) * divisor = B^3 - k for some 1 <= k <= divisor

Möller, Granlund, “Improved division by invariant integers”, Algorithm 6.

pub const fn new(divisor: u128) -> Self

Initialize from a given normalized divisor.

divisor must have top bit of 1

pub const fn div_rem_2by2(&self, a: u128) -> (u128, u128)

pub const fn div_rem_3by2(&self, a_lo: u64, a_hi: u128) -> (u64, u128)

The input a is arranged as (lo, mi & hi) The output is (a / divisor, a % divisor)

pub const fn div_rem_4by2(&self, a_lo: u128, a_hi: u128) -> (u128, u128)

Divdide a 4-word number with double word divisor

The output is (a / divisor, a % divisor)

impl Normalized3by2Divisor<usize, u128>

pub const fn invert_double_word(divisor: u128) -> usize

Calculate the inverse m > 0 of a normalized divisor (fit in a DoubleWord), such that

(m + B) * divisor = B^3 - k for some 1 <= k <= divisor

Möller, Granlund, “Improved division by invariant integers”, Algorithm 6.

pub const fn new(divisor: u128) -> Self

Initialize from a given normalized divisor.

divisor must have top bit of 1

pub const fn div_rem_2by2(&self, a: u128) -> (u128, u128)

pub const fn div_rem_3by2(&self, a_lo: usize, a_hi: u128) -> (usize, u128)

The input a is arranged as (lo, mi & hi) The output is (a / divisor, a % divisor)

pub const fn div_rem_4by2(&self, a_lo: u128, a_hi: u128) -> (u128, u128)

Divdide a 4-word number with double word divisor

The output is (a / divisor, a % divisor)

Trait Implementations

impl<T: Clone, D: Clone> Clone for Normalized3by2Divisor<T, D>

fn clone(&self) -> Normalized3by2Divisor<T, D>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, D: Debug> Debug for Normalized3by2Divisor<T, D>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq, D: PartialEq> PartialEq for Normalized3by2Divisor<T, D>

fn eq(&self, other: &Normalized3by2Divisor<T, D>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Copy, D: Copy> Copy for Normalized3by2Divisor<T, D>

impl<T: Eq, D: Eq> Eq for Normalized3by2Divisor<T, D>

impl<T, D> StructuralPartialEq for Normalized3by2Divisor<T, D>