Crate strength_reduce

Expand description

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.