strength_reduce

strength_reduce 通过“算术强度降低”实现整数除法和取模运算。

现代处理器在乘法和位移操作上比除法快得多，“算术强度降低”是一种将除法转换为乘法和位移的算法。编译器已经对编译时已知的除数执行了此优化；这个库使得在运行时也知道了除数的情况下执行此优化。

基准测试显示整数除法和取模运算的速度提高了5-10倍。

这个库适用于以下示例中的热点循环，其中在循环中多次重复除法，且除数保持不变。创建强度降低除法实例与设置成本相关，因此对于1-2次除法使用强度降低除法不值得设置成本。盈亏平衡点因用例而异，但通常较低：基准测试表明，使用同一个 StengthReduced## 实例进行3到4次重复除法是值得的。

strength_reduce 是 #![no_std]

有关更多信息，请参阅 API 文档。

示例

use strength_reduce::StrengthReducedU64;

let mut my_array: Vec<u64> = (0..500).collect();
let divisor = 3;
let modulo = 14;

// slow naive division and modulo
for element in &mut my_array {
    *element = (*element / divisor) % modulo;
}

// fast strength-reduced division and modulo
let reduced_divisor = StrengthReducedU64::new(divisor);
let reduced_modulo = StrengthReducedU64::new(modulo);
for element in &mut my_array {
    *element = (*element / reduced_divisor) % reduced_modulo;
}

测试

strength_reduce 使用 proptest 生成测试用例。此外，由于 u8 和 u16 的问题空间足够小，我们可以测试分子和除数的所有可能组合。但是，u16 的穷举测试需要几分钟才能运行，因此它被标记为 #[ignore]。在提交拉取请求之前，请至少使用 cargo test -- --ignored 测试一次。

兼容性

strength_reduce 包需要 rustc 1.26 或更高版本。

许可证

许可证为以下之一

• Apache License，版本 2.0，(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 https://opensource.org/licenses/MIT)

任选其一。