performance - 快速模数 511 和 127

有没有办法，如何比使用“%”运算符更快地使模数为 511(和 127)？

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

最佳答案

这是一种通过 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);



}

关于performance - 快速模数 511 和 127，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10259937/