按年被提到
20192019 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1902.01961 · cs.MS

Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries

通过直接计算更快地求余数:在编译器与软件库中的应用
Daniel Lemire, Owen Kaser, Nathan Kurz · 2019

用除数倒数的小数部分直接求余数,并给出更快的整除判断

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2019-02-08 · 最近 2025-06-06
3不同的人
3活跃月份
3讨论串
19被引(OpenAlex)

整数乘法比整数除法快得多,当除数已知或重复使用时,可用乘法代替除法。目前常量除法的余数是由商经一次乘法加一次减法得到的,若只需要余数则可能不是最优;论文提出通用算法,取被除数与除数倒数乘积的小数部分直接计算余数,并据此给出更简单的整除性检测算法和倒数精度的新紧界。作者的 C 实现在 Skylake、Ryzen 等 x64 处理器上最多比先进编译器生成的代码快超过 25%,整除判断函数在所有测试平台上比 Granlund-Montgomery 方法最多快超过 50%。

HN 为什么提它

HN 评论者把论文当作博客文章的更严谨版本,称其对 N 和快速取余技巧给出了更清晰的定义。

方法难度 3 / 5约 35 分钟经得起时间
读之前最好知道
1整数运算与定点表示
2编译器优化与常量除法
3C 语言与 x64 指令性能
4模运算基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐nkurz · 2019-02

“For the blog post, the actual article gives better definitions: Faster Remainder by Direct Computation.”

指出博客不如论文,论文对快速求余技巧定义更清楚
Faster remainders when the divisor is a constant: beating compilers & libdivide原评论 ↗
被提交为 story · 2 次