专用除法和余数算法

本 crate 不旨在直接使用，而是用于编译器（如 compiler-builtins）的某些部分，以便所有除法代码都能受益。然而，在需要控制内联的情况下（例如，查看使用内联来删除仅用于计算余数的指令的 u128_div_asymmetric 函数），此 crate 可能会找到用途。

本 crate 为四种不同的除法函数提供了算法、测试和基准测试

• 用于没有硬件除法器的 CPU 的 _binary_long 函数
• 类似于 _binary_long 的 _delegate 函数，但在可能的情况下调用更小的除法
• 设计用于除以大于 CPU 支持的最大的硬件除法的整数的 _trifecta 函数。这些函数对于具有和没有硬件除法器的 CPU 都非常高效。请注意，此函数依赖于快速的乘法器，因此即使有硬件除法器，在某些情况下 _delegate 也可以比此函数表现更好。
• 类似于 _trifecta 函数的 _asymmetric 函数，但针对具有不对称大小硬件除法函数的 CPU（如 x86_64 的除法指令）进行了优化

在不启用任何默认功能的情况下，此 crate 在 no_std 模式下运行，并且仅导出宏。当启用了 implement 和 std 标志时，此 crate 使用其宏来实现一系列用于测试和基准测试的除法函数。请注意，对于 _asymmetric 有效地运行，必须设置 asm 功能标志。

大多数除法算法最终都会进行大量工作以获取商和余数，这就是为什么这些函数返回两者（编译器可以内联并优化掉未使用的计算和结果）的原因。

关于命名规范：所有的 _div 函数实际上应该命名为 _quo（商）函数，这样可以避免与 div（除数）名称冲突。为了与 std 保持一致，它保持为 _div。 duo 这样命名是为了避免“被除数”和“除数”中的“div”冲突，并且因为在许多算法中，它在除法函数内部保持并从被除数中减去，直到成为余数（因此它同时作为被除数和余数使用）。

基准测试

使用默认功能在此库上运行 cargo bench 时，它将在随机数上运行除法操作，以基准测试不同范围的被除数和除数。

基准测试的名称指定了4件事

- 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.

例如，u128_div_rem_96_70_asymmetric 基准测试使用非对称算法找到 i128 随机整数（最高 128 - 96 = 32 位为零）除以 u128 随机整数（最高 128 - 70 = 58 位为零）的商和余数所需的时间。

在 Intel i3-3240 上，基准测试看起来像这样。此基准测试是在 Rust 1.46.0-nightly（8ac1525e0 2020-07-07）和默认功能下运行的。

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)