Debian Codegraph @

.cargo/vendor/strength_reduce/README.md

raw
1 # strength_reduce
2 [![crate](https://img.shields.io/crates/v/strength_reduce.svg)](https://crates.io/crates/strength_reduce)
3 [![license](https://img.shields.io/crates/l/strength_reduce.svg)](https://crates.io/crates/strength_reduce)
4 [![documentation](https://docs.rs/strength_reduce/badge.svg)](https://docs.rs/strength_reduce/)
5 ![minimum rustc 1.26](https://img.shields.io/badge/rustc-1.26+-red.svg)
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