高速モジュロ511と127

Question

"％"演算子を使用するよりも速く511（と127）でモジュロを作る方法はありますか？

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

Answer 1

事前に格納されているソリューションでルックアップテーブルを使用できます。あなたが100万の整数の配列を作成する場合は、実際にはC＃アプリケーションでモジュロを実行するのに比べて2倍の速さです。

// 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

多数のデータに対して2つのモジュラス演算を繰り返す必要があり、CPUがSIMD（たとえばIntelのSSE/AVX/AVX2）をサポートしている場合、演算をベクトル化できます。つまり、平行。これを行うには、組み込み関数またはインラインアセンブリを使用します。はい、解決策はプラットフォーム固有のものですが、おそらくそれは問題ありません。

Answer 3

ここでは、xが最大32767であると仮定して511でモジュロを高速化する方法があります。これは約x%511の約2倍です。これは5つのステップでモジュロを行います：2つの乗算、2つの加算、1つのシフト。

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

ここに私がこのように到着する際の理論があります。私たちならば今のテイラー展開に

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

を使用して、その後

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

、私はのは

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

はのは、z = 512を定義してみましょう考えるエンド

でこれをテストしたコードを掲載しましたxが限られた範囲を持っていることを知ってください。 xが常に2^15 = 32768以下であるとしましょう。

：その後、我々は、我々は三の段階で（X未満32768であると仮定して）X/511を分割することができる

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

到着有意である数字を見た後

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

を書き込むことができます

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



}