![Latest Release] ![Documentation] ![Minimum Supported Rust Version 1.54]
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 #![no_std] and #![forbid(unsafe_code)].
```rust use quickdiv::DivisorU64;
fn isquadraticresidue(q: u64, modulus: u64) -> bool { // Initializing a divisor is more expensive than a single unoptimized // division, to gain benefit you must divide multiple times by same divisor. let modulus = DivisorU64::new(modulus);
// The original value can be recovered using ::get().
for x in (0..modulus.get()) {
// A divisor can be used as the right-hand side operand with
// the / and % operators.
if (x * x) % modulus == q {
return true;
}
}
false
}
assert!(isquadraticresidue(152, 169)); assert!(!isquadraticresidue(51, 111)); ```
Licensed under any of:
by your choice.
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.