Specialized Division and Remainder Algorithms

This crate is not intended for direct use, but for use in parts of compilers (such as compiler-builtins), so that all division code can benefit. However, this crate might find use for cases where control over inlining is needed (e.g. see the u128_div_asymmetric function which uses inlining to remove instructions only needed for calculating the remainder).

This crate provides the algorithms, tests, and benchmarks for four different division functions:

• The _binary_long functions for CPUs without hardware dividers
• The _delegate functions similar to _binary_long, but with calls to smaller divisions if possible
• The _trifecta functions designed for dividing integers larger than the largest hardware division a CPU supports. These become efficient for 128 bit divisions, for both CPUs with and without hardware dividers. Note that this function depends upon fast multpliers, such that _delegate can outperform this function even with hardware dividers in some cases.
• The _asymmetric functions similar to the _trifecta functions, except optimized for CPUs with an asymmetric sized hardware division function such as x86_64's division instruction

Without any default features on, this crate is in no_std mode and only exports macros. When the implement and std flags are on, this crate uses its macros to implement a wide arrangement of division functions for usage in tests and benchmarks. Note that setting the the asm feature flag is absolutely required for _asymmetric to work efficiently.

Most division algorithms end up doing most of the work to get both the quotient and remainder, which is why these functions return both (and the compiler can inline and optimize away unused results and calculations).

On naming conventions: All _div functions should really be named _quo (quotient) functions, and it would stop the name collision with div for divisor, but to keep consistency with std it is kept as _div. duo is named as such to avoid the collision between the "div" in dividend and divisor, and because in many algorithms it is kept around and subtracted from inside division functions until it becomes the remainder (so it works as both the dividend and the remainder).

Benchmarks

When running cargo bench on this library with default features, it runs division operations on random numbers masked to benchmark different ranges of dividends and divisors.

The names of the benchmarks specify 4 things:

- the type of integer being operated on
- the size of the numbers being entered (specifically, how many lower bits of the random integer
  are being kept)
- the kind of algorithm. Whatever Rust's `/` and `%` operators are using is benchmarked by
  the `_std` benches.

For example, the u128_div_rem_96_70_asymmetric benchmark tests how long it takes to find the quotients and remainders of i128 random integers with the top 128 - 96 = 32 bits zeroed, divided by a u128 random integer with the top 128 - 70 = 58 bits zeroed, using the asymmetric algorithm.

On an Intel i3-3240, the benchmarks look like this. This benchmark was run on Rust 1.46.0-nightly (8ac1525e0 2020-07-07) with default features:

test i128_div_rem_96_32_asymmetric   ... bench:          29 ns/iter (+/- 0)
test i128_div_rem_96_32_delegate     ... bench:          32 ns/iter (+/- 5)
test i128_div_rem_96_32_std          ... bench:         203 ns/iter (+/- 3)
test i128_div_rem_96_32_trifecta     ... bench:          33 ns/iter (+/- 0)
test u128_div_rem_120_120_asymmetric ... bench:          21 ns/iter (+/- 0)
test u128_div_rem_120_120_delegate   ... bench:          16 ns/iter (+/- 0)
test u128_div_rem_120_120_std        ... bench:          24 ns/iter (+/- 2)
test u128_div_rem_120_120_trifecta   ... bench:          14 ns/iter (+/- 0)
test u128_div_rem_128_64_asymmetric  ... bench:          37 ns/iter (+/- 1)
test u128_div_rem_128_64_delegate    ... bench:          86 ns/iter (+/- 7)
test u128_div_rem_128_64_std         ... bench:         218 ns/iter (+/- 62)
test u128_div_rem_128_64_trifecta    ... bench:          61 ns/iter (+/- 1)
test u128_div_rem_128_8_asymmetric   ... bench:          30 ns/iter (+/- 0)
test u128_div_rem_128_8_delegate     ... bench:          31 ns/iter (+/- 2)
test u128_div_rem_128_8_std          ... bench:         371 ns/iter (+/- 2)
test u128_div_rem_128_8_trifecta     ... bench:          34 ns/iter (+/- 0)
test u128_div_rem_128_96_asymmetric  ... bench:          41 ns/iter (+/- 0)
test u128_div_rem_128_96_delegate    ... bench:          55 ns/iter (+/- 4)
test u128_div_rem_128_96_std         ... bench:         119 ns/iter (+/- 0)
test u128_div_rem_128_96_trifecta    ... bench:          43 ns/iter (+/- 1)
test u128_div_rem_96_32_asymmetric   ... bench:          27 ns/iter (+/- 0)
test u128_div_rem_96_32_delegate     ... bench:          54 ns/iter (+/- 1)
test u128_div_rem_96_32_std          ... bench:         212 ns/iter (+/- 2)
test u128_div_rem_96_32_trifecta     ... bench:          33 ns/iter (+/- 0)
test u128_div_rem_96_70_asymmetric   ... bench:          21 ns/iter (+/- 0)
test u128_div_rem_96_70_delegate     ... bench:          46 ns/iter (+/- 0)
test u128_div_rem_96_70_std          ... bench:          97 ns/iter (+/- 0)
test u128_div_rem_96_70_trifecta     ... bench:          24 ns/iter (+/- 0)
(the rest of the benchmarks are not included here, because the 64 bit hardware divisions are always
faster than the algorithms)