3

最大値までの整数に対して、遅延フィボナッチ疑似乱数ジェネレーターを実装しようとしています。値の配列を維持します

int values[SIZE] = { /* 55 seed values */ };

次の関数を使用して次の値を返します

unsigned lagfib()
{
    static unsigned idx = 0;
    int r = values[idx];

    /* The following does not work: */
    values[idx] = (values[(idx-24) % SIZE] + values[(idx-55) % SIZE])
                 % MAX_VALUE;
    idx = (idx+1) % SIZE;
    return r;
}

実際にvaluesは、常に満杯の単純なリング バッファにする必要があります。減算とモジュロは、インデックスを配列の末尾にラップする必要があります。SIZEは常に少なくとも 55 である必要がありますが、モジュロを高速化するために 64 に切り上げたいと考えています。

しかしどうやら、モジュロ計算が間違っていて、修正方法がわかりません。インデックスの種類を に変更しintても改善されません。

(PS .: はい、staticdata は悪いスタイルですが、C と C++ の両方のプログラマーが読めるようにしたいのです。これは両方の言語に関係するからです。)

4

3 に答える 3

3

idx = 0とを取りましょうSIZE = 64。

(idx-24) % SIZE unsigned の場合は非常に大きな値 ( 429496727232 ビット int の場合) にidxなり、無効なインデックスになります。

循環効果を得るには、モジュラスを取得するSIZE 前に追加する必要があります。

(idx-24+SIZE) % SIZE と(0-24+64)%64評価され40ます。

于 2010-10-18T13:02:34.630 に答える
2

たとえばidxが 24 未満の場合、 の数値範囲のもう一方の端にラップアラウンドしますunsigned int。55 は 2^32 などの除数ではないため、正しい結果が得られません。

2 つのオプションが表示されます。

  • idxそれぞれ 24 と 55 オフセットされた3 つの個別の変数を維持します。
  • などを行います(idx - 24 + SIZE) % SIZE。

実際には、最初のオプションを選択し、インクリメントを次のように書き換えてモジュロを完全に回避します。

idx = ((SIZE-1) == idx) ? 0 : (idx+1);

おそらく、モジュロを計算するよりもはるかに高速です。

于 2010-10-18T13:01:52.167 に答える
0

負のインデックスで値にアクセスしています。例えば：

-24 % 55 == -24

そのため、配列の最後までラップアラウンドするためのロジックが必要になります。C/C++ はこれを行いません。

于 2010-10-18T13:02:16.097 に答える