Geek Answers Handbook

Effective modem 3 in x86 assembly

Instructions DIVfor modern processors are expensive. Is there a faster way to reduce the 64-bit integer mod 3 in x86 assembly?

+6
source share
1 answer

There are algorithms for this, based on performing division by multiplication with the inverse divider. There are various documents about this, the most frequently mentioned:

Thorbjörn Granlund and Peter L. Montgomery. "Division into invariant integers using multiplication." ACM SIGPLAN Notifications. Volume 29, No. 6, August 1994, pp. 61-72 (online)

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
+8

More articles:


All Articles