x86汇编中的高效mod 3

Question

该DIV指令在现代处理器上很昂贵.有没有更快的方法来减少x86汇编中的64位整数mod 3？

Answer 1

有这样的算法,基于通过乘以除数的倒数进行除法.有关于此的各种论文,最常被引用的是:

TorbjörnGranlund和Peter L. Montgomery."使用乘法除以不变整数." ACM SIGPLAN通知.卷.1994年8月29日第6期,第61-72页(在线)

在启用优化时,您的C/C++编译器很可能已使用此算法的变体.例如,我的英特尔编译器,版本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