3 releases
0.1.2 | May 28, 2021 |
---|---|
0.1.1 | May 13, 2021 |
0.1.0 | May 12, 2021 |
#1613 in Algorithms
17KB
218 lines
Baseline implementation of division by constants
When dividing integers by compile-time constants, compilers (LLVM) can be trusted to convert those to a sequence of multiplication and shift.
That doesn't work so well when the constant isn't known until runtime.
This crate implements a simple strategy with reliable performance. Does reliable imply good? For this application, it does.
The basic PartialReciprocal
should be compiled to a constant-time
fast path, and can handle every divisor except 0, 1, and u64::MAX
.
The slightly more complex Reciprocal
can also divide by 1 and
u64::MAX
, at the expense of one more u64
field, and a slightly
more complex (one more load, maybe one more integer arithmetic
instruction) fast path.