Fast Modulo 511和127

Question

有沒有辦法，比使用「％」運算符更快地進行模511（和127）？

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

Answer 1

您可以使用預先存儲解決方案的查找表。如果創建一個包含一百萬個整數的數組，查找速度幾乎是我的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]; 

這將花費你（可能很多）內存，如果你想用它顯然不會工作，也是非常大的數字。但速度更快。

Answer 2

如果你要重複上的大量數據的這兩個模運算和你的CPU支持SIMD（例如Intel的SSE/AVX/AVX2），那麼你可以向量化的操作，即做對許多數據的操作平行。您可以通過使用內部函數或內聯彙編來完成此操作。是的解決方案將是平臺特定的，但也許這是很好的...

Answer 3

這是一種快速取模的方法，假設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); 



}