4

有没有办法，如何使 511（和 127）的模数比使用“%”运算符更快？

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

3 回答 3

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 位发布模式下分析此代码的代码。

#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);



}
于 2014-02-17T10:59:19.903 回答
0

您可以使用预先存储解决方案的查找表。如果您创建一个包含一百万个整数的数组，那么查找的速度大约是在我的 C# 应用程序中实际执行取模的速度的两倍。

// fill an array
var mod511 = new int[1000000];
for (int x = 0; x < 1000000; x++) mod511[x] = x % 511;

而不是使用

c = 758 % 511;

你用

c = mod511[758];

这将花费您（可能很多）内存，并且如果您也想将它用于非常大的数字，显然将无法正常工作。但它更快。

于 2012-06-28T11:08:06.840 回答
0

如果您必须对大量数据重复这两个模数运算并且您的 CPU 支持 SIMD（例如 Intel 的 SSE/AVX/AVX2），那么您可以对这些运算进行矢量化，即并行对许多数据进行运算。您可以通过使用内在函数或内联汇编来做到这一点。是的，解决方案将是特定于平台的，但也许这很好......

于 2014-02-15T13:15:48.257 回答