Crate strength_reduce

strength_reduce implements integer division and modulo via "arithmetic strength reduction"

This results in much better performance when computing repeated divisions or modulos.

Example:

use strength_reduce::StrengthReducedU64;
 
let mut my_array: Vec<u64> = (0..500).collect();
let divisor = 3;
let modulo = 14;

// slow naive division and modulo
for element in &mut my_array {
    *element = (*element / divisor) % modulo;
}

// fast strength-reduced division and modulo
let reduced_divisor = StrengthReducedU64::new(divisor);
let reduced_modulo = StrengthReducedU64::new(modulo);
for element in &mut my_array {
    *element = (*element / reduced_divisor) % reduced_modulo;
}

The intended use case for StrengthReducedU## is for use in hot loops like the one in the example above: A division is repeated hundreds of times in a loop, but the divisor remains unchanged. In these cases, strength-reduced division and modulo are 5x-10x faster than naive division and modulo.

There is a setup cost associated with creating stength-reduced division instances, so using strength-reduced division for 1-2 divisions is not worth the setup cost. The break-even point differs by use-case, but appears to typically be around 5-10 for u8-u32, and 30-40 for u64.

For divisors that are known at compile-time, the compiler is already capable of performing arithmetic strength reduction. But if the divisor is only known at runtime, the compiler cannot optimize away the division. strength_reduce is designed for situations where the divisor is not known until runtime.

strength_reduce is #![no_std]

The optimizations that this library provides are inherently dependent on architecture, compiler, and platform, so test before you use.

Structs

StrengthReducedU8	Implements unsigned division and modulo via mutiplication and shifts.
StrengthReducedU16	Implements unsigned division and modulo via mutiplication and shifts.
StrengthReducedU32	Implements unsigned division and modulo via mutiplication and shifts.
StrengthReducedU64	Implements unsigned division and modulo via mutiplication and shifts.
StrengthReducedUsize	Implements unsigned division and modulo via mutiplication and shifts.