Faster integer division and modulus operations.
strength_reduce uses arithmetic strength reduction to transform divisions into multiplications and shifts.
When the divisor is not known at compile time, this yields a 5x-10x speedup for integer division and modulo operations,
with a small amortized setup cost.
This library is intended for hot loops like the example below, where a division is repeated hundreds of times in a loop, but the divisor remains unchanged. 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.
strength_reduce is #![no_std]
See the API Documentation for more details.
```rust use strength_reduce::StrengthReducedU64;
let mut my_array: Vec
// slow naive division and modulo for element in &mut my_array { element = (element / divisor) % modulo; }
// fast strength-reduced division and modulo let reduceddivisor = StrengthReducedU64::new(divisor); let reducedmodulo = StrengthReducedU64::new(modulo); for element in &mut myarray { *element = (*element / reduceddivisor) % reduced_modulo; } ```
strength_reduce uses proptest to generate test cases. In addition, the u8 and u16 problem spaces are small enough that we can exhaustively test every possible combination of numerator and divisor.
However, the u16 exhaustive test takes several minutes to run, so it is marked #[ignore]. Before submitting pull requests, please test with cargo test -- --ignored at least once.
The strength_reduce crate requires rustc 1.26 or greater.
Licensed under either of
at your option.