x86 汇编中的高效 mod 3

Question

DIV 指令在 modern 处理器上很昂贵。有没有更快的方法来减少 x86 程序集中的 64 位整数 mod 3？

Answer 1

有基于除数乘以除数倒数的算法。关于这个有很多论文，最常被引用的一篇是：

Torbjörn Granlund 和 Peter L. Montgomery。 "Division by invariant integers using multiplication." ACM SIGPLAN 通知。卷。 29，第 6 期，1994 年 8 月，第 61-72 页 (online)

您的 C/C++ 编译器很可能在打开优化时已经使用了该算法的变体。例如，我的 Intel 编译器版本 13 会变成这样：

#include <stdint.h>
uint64_t mod3 (uint64_t a)
{
    return a % 3;
}

进入此（我的行尾注释）：

mod3    PROC
; parameter 1: rcx
        mov       r8, 0aaaaaaaaaaaaaaabH      ;; (scaled) reciprocal of 3
        mov       rax, rcx
        mul       r8                          ;; multiply with reciprocal
        shr       rdx, 1                      ;; quotient
        lea       r9, QWORD PTR [rdx+rdx*2]   ;; back multiply with 3
        neg       r9
        add       rcx, r9                     ;; subtract from dividend 
        mov       rax, rcx                    ;; remainder
        ret
mod3    ENDP

x86 汇编中的高效 mod 3

Efficient mod 3 in x86 assembly

assembly

x86-64

micro-optimization