4

「%」演算子を使用するよりもモジュロを 511 (および 127) 速くする方法はありますか?

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

3 に答える 3

1

x が最大 32767 であると仮定して、511 によるモジュロを高速に実行する方法を次に示しますx%511。モジュロは 5 つのステップで実行されます: 乗算 2 回、加算 2 回、シフト 1 回です。

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 未満であると仮定) を次の 3 つのステップで割ることができます。

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

ソリューションが事前に保存されているルックアップ テーブルを使用できます。100 万個の整数の配列を作成すると、C# アプリで実際に modulo を実行する場合の約 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];

これは (おそらく大量の) メモリを消費し、非常に大きな数に対しても使用したい場合には明らかに機能しません。しかし、それはより高速です。

于 2012-06-28T11:08:06.840 に答える
0

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

于 2014-02-15T13:15:48.257 に答える