| 1 |
# strength_reduce |
| 2 |
[](https://crates.io/crates/strength_reduce) |
| 3 |
[](https://crates.io/crates/strength_reduce) |
| 4 |
[](https://docs.rs/strength_reduce/) |
| 5 |
 |
| 6 |
|
| 7 |
`strength_reduce` implements integer division and modulo via "arithmetic strength reduction". |
| 8 |
|
| 9 |
Modern processors can do multiplication and shifts much faster than division, and "arithmetic strength reduction" is an algorithm to transform divisions into multiplications and shifts. |
| 10 |
Compilers already perform this optimization for divisors that are known at compile time; this library enables this optimization for divisors that are only known at runtime. |
| 11 |
|
| 12 |
Benchmarking shows a 5-10x speedup on integer division and modulo operations. |
| 13 |
|
| 14 |
This library is intended for hot loops like the example below, where a division is repeated many times in a loop with the divisor remaining 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 is typically low: Benchmarking has shown that takes 3 to 4 repeated divisions with the same StengthReduced## instance to be worth it. |
| 15 |
|
| 16 |
`strength_reduce` is `#![no_std]` |
| 17 |
|
| 18 |
See the [API Documentation](https://docs.rs/strength_reduce/) for more details. |
| 19 |
|
| 20 |
## Example |
| 21 |
```rust |
| 22 |
use strength_reduce::StrengthReducedU64; |
| 23 |
|
| 24 |
let mut my_array: Vec<u64> = (0..500).collect(); |
| 25 |
let divisor = 3; |
| 26 |
let modulo = 14; |
| 27 |
|
| 28 |
// slow naive division and modulo |
| 29 |
for element in &mut my_array { |
| 30 |
*element = (*element / divisor) % modulo; |
| 31 |
} |
| 32 |
|
| 33 |
// fast strength-reduced division and modulo |
| 34 |
let reduced_divisor = StrengthReducedU64::new(divisor); |
| 35 |
let reduced_modulo = StrengthReducedU64::new(modulo); |
| 36 |
for element in &mut my_array { |
| 37 |
*element = (*element / reduced_divisor) % reduced_modulo; |
| 38 |
} |
| 39 |
``` |
| 40 |
|
| 41 |
## Testing |
| 42 |
|
| 43 |
`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. |
| 44 |
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. |
| 45 |
|
| 46 |
## Compatibility |
| 47 |
|
| 48 |
The `strength_reduce` crate requires rustc 1.26 or greater. |
| 49 |
|
| 50 |
## License |
| 51 |
|
| 52 |
Licensed under either of |
| 53 |
|
| 54 |
* Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0) |
| 55 |
* MIT license ([LICENSE-MIT](LICENSE-MIT) or https://opensource.org/licenses/MIT) |
| 56 |
|
| 57 |
at your option. |
| 58 |
|