6

特にGeorge MarsagliaのXOR-Shift RNGの疑似乱数ジェネレーターの実装があります。私の実装はここにあります：

FastRandom.cs

最初のランダム サンプルはシードと非常に密接に相関していることがわかります。これは、Reinitialise(int シード) メソッドを見れば明らかです。これは悪いです。私が提案する解決策は、シードのビットを次のように混同することです。

_x = (uint)(  (seed * 2147483647) 
           ^ ((seed << 16 | seed >> 48) * 28111) 
           ^ ((seed << 32 | seed >> 32) * 69001)
           ^ ((seed << 48 | seed >> 16) * 45083));

そのため、シードのビットを 4 つの素数で乗算し、XOR 演算を行って _x を形成することにより、相関関係を大幅に弱めました。また、乗算の前にシードのビットをローテーションして、さまざまな大きさのビットが 32 ビット値の値の全範囲で混同されるようにします。

4 方向ローテーションは、何もしないことと可能なすべてのローテーション (32) の間のバランスが良いように見えました。素数は「空中の指」です。開始シードに関係なく、ビットをごちゃまぜにして32ビット全体に「広げる」のに十分な大きさとビット構造です。

より大きな素数を使用する必要がありますか? この問題に対する標準的なアプローチはありますか?おそらくより正式な根拠がありますか? 最小限の CPU オーバーヘッドでこれを実行しようとしています。

ありがとう

===更新===

32 ビットすべてに分散されたセット ビットを使用して、いくつかの素数を使用することにしました。その結果、乗算が同じ効果 (32 ビットの全範囲にわたってビットをハッシュする) を達成するため、シフトを省略できるので、最終的なシードを与えるために 4 つの積を追加するだけです...

_x = (uint)(  (seed * 1431655781) 
            + (seed * 1183186591) 
            + (seed * 622729787)
            + (seed * 338294347));

素数/乗算を少なくすることでうまくいく可能性があります。2 つが少なすぎるように見え (最初のサンプルではまだパターンを確認できました)、3 つが問題ないように見えたので、安全マージンとして 4 つにしました。

=== 更新 2 ===

参考までに、上記は機能的に同等のものに縮小されます。

_x = seed * 3575866506U;

私は最初にこれを見つけませんでした。私が見つけたとき、計算のさまざまな段階でオーバーフローすると別の結果が生じるのではないかと思っていました。答えはノーだと思います - 2 つの計算は常に同じ答えを返します。

4

1 に答える 1

2

一部の研究者によると、CrapWow、Crap8、Murmur3は、現在利用可能な最高の非暗号化ハッシュ アルゴリズムであり、高速かつシンプルで、統計的に優れています。

詳細については、Non-Cryptographic Hash Function Zooを参照してください。

編集: 2021 年 5 月現在、非暗号化ハッシュ関数 Zoo への floodberry.com リンクは有効ではありません。コンテンツは今でもarchive.orgで見つけることができます。

于 2013-02-23T21:02:41.837 に答える