performance - 快速模 511 和 127

Question

有没有办法比使用“%”运算符更快地对 511(和 127)求模？

int c = 758 % 511;
int d = 423 % 127;

Answer 1

这是一种快速对 511 取模的方法，假设 x 最多为 32767。它的速度大约是 x%511 的两倍。它分五步进行求模:两次乘法、两次加法、一次移位。

inline int fast_mod_511(int x) {
    int y = (513*x+64)>>18;
    return x - 511*y;
}

这是我如何得出这个结论的理论。我在最后发布了我测试过的代码

让我们考虑一下

y = x/511 = x/(512-1) = x/1000 * 1/(1-1/512).

让我们定义 z = 512，然后

y = x/z*1/(1-1/z).

使用泰勒展开式

y = x/z(1 + 1/z + 1/z^2 + 1/z^3 + ...).

现在，如果我们知道 x 的范围有限，我们就可以削减扩展。假设 x 始终小于 2^15=32768。然后我们就可以这样写

512*512*y = (1+512)*x = 513*x.

查看了重要的数字后，我们得出

y = (513*x+64)>>18 //512^2 = 2^18.

我们可以将 x/511(假设 x 小于 32768)分为三步:

multiply,
add,
shift.

下面是我在 Ivy Bridge 核心上的 MSVC2013 64 位 Release模式下进行分析的代码。

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

inline int fast_mod_511(int x) {
    int y = (513*x+64)>>18;
    return x - 511*y;
}

int main() {
    unsigned int i, x;
    volatile unsigned int r;
    double dtime;

    dtime = omp_get_wtime();
    for(i=0; i<100000; i++) {
        for(int j=0; j<32768; j++) {
            r = j%511;
        }     
    }
    dtime =omp_get_wtime() - dtime;
    printf("time %f\n", dtime);

    dtime = omp_get_wtime();
    for(i=0; i<100000; i++) {
        for(int j=0; j<32768; j++) {
            r = fast_mod_511(j);
        }
    }
    dtime =omp_get_wtime() - dtime;
    printf("time %f\n", dtime);



}