Struct Normalized2by1Divisor

pub struct Normalized2by1Divisor<T> { /* private fields */ }

Divide a DoubleWord by a prearranged divisor.

Assumes quotient fits in a Word.

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

Implementations

impl Normalized2by1Divisor<u8>

pub const fn invert_word(divisor: u8) -> u8

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

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

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

Initialize from a given normalized divisor.

The divisor must have top bit of 1

pub const fn div_rem_1by1(&self, a: u8) -> (u8, u8)

Returns (a / divisor, a % divisor)

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

Returns (a / divisor, a % divisor) The result must fit in a single word.

impl Normalized2by1Divisor<u16>

pub const fn invert_word(divisor: u16) -> u16

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

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

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

Initialize from a given normalized divisor.

The divisor must have top bit of 1

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

Returns (a / divisor, a % divisor)

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

Returns (a / divisor, a % divisor) The result must fit in a single word.

impl Normalized2by1Divisor<u32>

pub const fn invert_word(divisor: u32) -> u32

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

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

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

Initialize from a given normalized divisor.

The divisor must have top bit of 1

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

Returns (a / divisor, a % divisor)

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

Returns (a / divisor, a % divisor) The result must fit in a single word.

impl Normalized2by1Divisor<u64>

pub const fn invert_word(divisor: u64) -> u64

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

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

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

Initialize from a given normalized divisor.

The divisor must have top bit of 1

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

Returns (a / divisor, a % divisor)

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

Returns (a / divisor, a % divisor) The result must fit in a single word.

impl Normalized2by1Divisor<usize>

pub const fn invert_word(divisor: usize) -> usize

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

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

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

Initialize from a given normalized divisor.

The divisor must have top bit of 1

pub const fn div_rem_1by1(&self, a: usize) -> (usize, usize)

Returns (a / divisor, a % divisor)

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

Returns (a / divisor, a % divisor) The result must fit in a single word.

Trait Implementations

impl<T: Clone> Clone for Normalized2by1Divisor<T>

fn clone(&self) -> Normalized2by1Divisor<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Normalized2by1Divisor<T>

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

Formats the value using the given formatter.

impl<T: PartialEq> PartialEq for Normalized2by1Divisor<T>

fn eq(&self, other: &Normalized2by1Divisor<T>) -> 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> Copy for Normalized2by1Divisor<T>

impl<T: Eq> Eq for Normalized2by1Divisor<T>

impl<T> StructuralPartialEq for Normalized2by1Divisor<T>