### 6 releases

Uses old Rust 2015

0.2.4 | Nov 8, 2022 |
---|---|

0.2.3 | Dec 27, 2019 |

0.2.2 | Jun 12, 2019 |

0.2.1 | Jan 5, 2019 |

0.1.1 | Jan 3, 2019 |

#**34** in Algorithms

**227,040** downloads per month

Used in **511** crates
(10 directly)

**MIT/Apache**

54KB

727 lines

# strength_reduce

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

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. 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.

Benchmarking shows a 5-10x speedup on integer division and modulo operations.

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.

is `strength_reduce``#!``[``no_std``]`

See the API Documentation for more details.

## 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`;`
`}`

## Testing

uses `strength_reduce`

to generate test cases. In addition, the `proptest`

and `u8`

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 `u16`

. Before submitting pull requests, please test with `#``[``ignore``]`

at least once.`cargo`` test --`

`--ignored`

## Compatibility

The

crate requires rustc 1.26 or greater.`strength_reduce`

## License

Licensed under either of

- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)

at your option.