推荐nkurz · 2019-02
“For the blog post, the actual article gives better definitions: Faster Remainder by Direct Computation.”
指出博客不如论文,论文对快速求余技巧定义更清楚
用除数倒数的小数部分直接求余数,并给出更快的整除判断
整数乘法比整数除法快得多,当除数已知或重复使用时,可用乘法代替除法。目前常量除法的余数是由商经一次乘法加一次减法得到的,若只需要余数则可能不是最优;论文提出通用算法,取被除数与除数倒数乘积的小数部分直接计算余数,并据此给出更简单的整除性检测算法和倒数精度的新紧界。作者的 C 实现在 Skylake、Ryzen 等 x64 处理器上最多比先进编译器生成的代码快超过 25%,整除判断函数在所有测试平台上比 Granlund-Montgomery 方法最多快超过 50%。
HN 评论者把论文当作博客文章的更严谨版本,称其对 N 和快速取余技巧给出了更清晰的定义。
“For the blog post, the actual article gives better definitions: Faster Remainder by Direct Computation.”