### 2 releases

0.1.1 | Oct 11, 2023 |
---|---|

0.1.0 | Sep 12, 2023 |

#**843** in Algorithms

**78** downloads per month

Used in **5** crates
(4 directly)

**Zlib OR Apache-2.0 OR MIT**

33KB

531 lines

# QuickDiv

QuickDiv is a Rust crate that allows you to speed up repeated division and modulo operations by the same divisor, based on the libdivide C/C++ library.

On most hardware today integer division operations take longer to execute compared to operations like multiplication and addition. Because of this, compilers generally optimize division by a constant, by replacing it with a cheaper sequence of shifts, multiplications and additions. This crate lets you apply a similar algorithm to optimize division by values that are only known at runtime.

Performance gains will vary between platforms, CPUs, and integer widths, but you can expect dividing an integer by a precomputed divisor to be somewhere between 2 to 10 times faster compared to the built-in hardware division method. Note that preparing the divisor is more expensive than a single unoptimized division: it will take at least 2 divisions by the same divisor to break even.

This crate supports primitive integer types of all widths, in both signed and
unsigned variants. It requires Rust version 1.54 or greater. It is

and `#!``[``no_std``]`

.`#!``[``forbid``(``unsafe_code``)``]`

## Example

`use` `quickdiv``::`DivisorU64`;`
`fn` `is_quadratic_residue``(``q``:` `u64`, `modulus``:` `u64``)`` ``->` `bool` `{`
`//` Initializing a divisor is more expensive than a single
`//` unoptimized division, to gain a benefit you must divide
`//` multiple times by the same divisor.
`let` modulus `=` `DivisorU64``::`new`(`modulus`)``;`
`//` The original value can be recovered by using ::get().
`for` x `in` `(``0``..`modulus`.``get``(``)``)` `{`
`//` A divisor can be used as the second operand with
`//` the / and % operators.
`if` `(`x `*` x`)` `%` modulus `==` q `{`
`return` `true``;`
`}`
`}`
`false`
`}`
`assert!``(``is_quadratic_residue``(``152``,` `169``)``)``;`
`assert!``(``!``is_quadratic_residue``(``51``,` `111``)``)``;`

## Performance

The following benchmarks should give a rough sense of the kind of speed-up you
can expect. The numbers represent throughput in millions of elements per second
(larger is better) on various tasks.
For

we divide a collection of random integers by a fixed
divisor, in `Quotient Sum`

we compute the remainder given a fixed modulus
and, finally, in `LCG`

we check the divisibility of random integers by a
fixed divisor.`FizzBuzz`

Task | CPU | Compiler | QuickDiv |
---|---|---|---|

Quotient Sum | 248.3 | 838 | 823.5 |

LCG | 168.8 | 252.7 | 255 |

FizzBuzz | 41.13 | 1350 | 556 |

Note that while QuickDiv computes the remainder and checks if its
zero, the compiler uses a different method to directly check divisibility,
leading to faster performance on the

task.`FizzBuzz`

### Caveats

- These results are for

only. Performance can vary with width and signedness.`u64` - Benchmarks were run on an AMD Ryzen 5 2600 CPU (i.e. an older x86-64 CPU). Some newer high-end processors like the Apple M1/M2 have very fast hardware division, and will experience a less dramatic speed-up.
- All tasks involved at least 1000 repeated uses of the same divisor, making branch prediction trivial. You will experience worse performance if you are instead iterating over a collection of different divisors. If you want to read more about this, check out Paul Khuong's post about his branchfree Rust integer division library Reciprocal.

If you would like to run these benchmarks yourself, check out the

crate in the GitHub
repository.`benchmarks`

## License

Licensed under any of:

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

by your choice.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be multi-licensed as above, without any additional terms or conditions.