Expand description
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.
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));Structs
- Faster divisor for division and modulo operations by 8-bit signed integer values.
- Faster divisor for division and modulo operations by 16-bit signed integer values.
- Faster divisor for division and modulo operations by 32-bit signed integer values.
- Faster divisor for division and modulo operations by 64-bit signed integer values.
- Faster divisor for division and modulo operations by 128-bit signed integer values.
- Faster divisor for division and modulo operations by pointer-sized signed integer values.
- Faster divisor for division and modulo operations by 8-bit unsigned integer values.
- Faster divisor for division and modulo operations by 16-bit unsigned integer values.
- Faster divisor for division and modulo operations by 32-bit unsigned integer values.
- Faster divisor for division and modulo operations by 64-bit unsigned integer values.
- Faster divisor for division and modulo operations by 128-bit unsigned integer values.
- Faster divisor for division and modulo operations by pointer-sized unsigned integer values.