4

私はrand_rインターフェイスの許容品質バージョンを実装しようとしていますが、これには、全体の状態が type の単一のオブジェクトに格納されるという残念なインターフェイス要件があります。unsignedこれは、私の目的では正確に 32 ビットを意味します。さらに、出力範囲を にする必要があります[0,2³¹-1]。標準的な解決策は、LCG を使用して下位ビット (周期が最も短い) をドロップすることですが、それでも次の数ビットの周期が非常に悪くなります。

私が最初に考えたのは、LCG を 2 回または 3 回繰り返して、出力の高/低または高/中/低ビットを生成することでした。ただし、このようなアプローチでは偏りのない分布は維持されません。各出力値の頻度が等しいのではなく、多くは複数回発生し、まったく発生しないものもあります。

状態は 32 ビットしかないため、PRNG の周期は 2³² に制限されます。偏りをなくすために、PRNG は各値を完全な周期の場合は正確に 2 回出力し、周期が 2³¹ の場合は正確に 1 回出力する必要があります。より短い期間は偏りがありません。

これらの基準を満たすよく知られた PRNG アルゴリズムはありますか?

4

4 に答える 4

3

32 ビットの最大周期ガロア LFSR が適している場合があります。試す：

r = (r >> 1) ^ (-(r & 1) & 0x80200003);

LFSR の 1 つの問題は、値 0 を生成できないことです。したがって、この値の範囲は 1 から 2^32-1 です。出力を微調整するか、適切な LCG に固執することをお勧めします。

于 2013-06-11T03:05:00.340 に答える
2

私のコメントを詳しく説明しています...

カウンター モードのブロック暗号は、おおよそ次の形式のジェネレーターを提供します (はるかに大きなデータ型を使用する場合を除く)。

uint32_t state = 0;
uint32_t rand()
{
    state = next(state);
    return temper(state);
}

暗号化セキュリティは指定されていないため (そして 32 ビットでは多かれ少なかれ無駄になります)、より単純なアドホックなテンパリング関数でうまくいくはずです。

1 つのアプローチは、next()関数が単純で (例: return state + 1;)、temper()複雑であることで補う (ブロック暗号のように) 場合です。

よりバランスの取れたアプローチは、LCG を に実装するnext()ことです。これは、すべての可能な状態をランダムな (っぽい) 順序で訪問することもわかっているため、temper()LCG の残りの問題をカバーするのに十分な作業を行う実装を見つけることです。

Mersenne Twister には、その出力にこのようなテンパリング機能が含まれています。それが適しているかもしれません。また、この質問は、要件を満たす操作を求めます。

これは、単語をビット反転し、定数 (奇数) を掛けることです。ビットリバースがアーキテクチャのネイティブ操作でない場合、これは非常に複雑になる可能性があります。

于 2013-06-11T23:33:58.417 に答える