Trait common_traits::FastRange

pub trait FastRange: Integer + Sized {
    type MaskType: Integer + Copy;

    // Required methods
    fn fast_range(&self, d: Self) -> Self;
    fn fast_div_mask(&self, mask: Self::MaskType) -> Self;
    fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self;
    fn compute_mask_fast(&self) -> Self::MaskType;
    fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool;

    // Provided methods
    fn fast_div(&self, d: Self) -> Self { ... }
    fn fast_mod(&self, d: Self) -> Self { ... }
    fn fast_is_divisible(&self, d: Self) -> bool { ... }
}

Fast division, modulo reduction, and an alternative operation that maps a number between 0 and n.

Reference

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://github.com/lemire/fastmod https://github.com/lemire/fastrange

Required Associated Types

type MaskType: Integer + Copy

Required Methods

fn fast_range(&self, d: Self) -> Self

Given a value “UnsignedInt”, produces an integer in [0,p) without division. The function is as fair as possible in the sense that if you iterate through all possible values of “UnsignedInt”, then you will generate all possible outputs as uniformly as possible.

This is equivalent to computing ⌊n * (UnsignedInt / 2^w)⌋ in fixed comma

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fastmod computes (a % d) given precomputed M,

fn compute_mask_fast(&self) -> Self::MaskType

Compute the mask needed by fast_div_mask and fast_mod_mask M = floor( (1<<64) / d ) + 1

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

fastmod computes (a % d) == 0 given precomputed M,

Provided Methods

fn fast_div(&self, d: Self) -> Self

fn fast_mod(&self, d: Self) -> Self

fastmod computes (a % d)

fn fast_is_divisible(&self, d: Self) -> bool

checks whether n % d == 0

Object Safety

This trait is not object safe.

Implementations on Foreign Types

impl FastRange for u8

type MaskType = u16

fn fast_range(&self, d: Self) -> Self

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fn compute_mask_fast(&self) -> Self::MaskType

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

impl FastRange for u16

type MaskType = u32

fn fast_range(&self, d: Self) -> Self

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fn compute_mask_fast(&self) -> Self::MaskType

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

impl FastRange for u32

type MaskType = u64

fn fast_range(&self, d: Self) -> Self

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fn compute_mask_fast(&self) -> Self::MaskType

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

impl FastRange for u64

type MaskType = u128

fn fast_range(&self, d: Self) -> Self

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fn compute_mask_fast(&self) -> Self::MaskType

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

impl FastRange for usize

type MaskType = u128

fn fast_range(&self, d: Self) -> Self

fn fast_div_mask(&self, mask: Self::MaskType) -> Self

fn fast_mod_mask(&self, d: Self, mask: Self::MaskType) -> Self

fn compute_mask_fast(&self) -> Self::MaskType

fn fast_is_divisible_mask(&self, mask: Self::MaskType) -> bool

Implementors