かつて、遺伝的アルゴリズムを実装するために128ビットの乱数を生成するタスクに直面しました。 タスクのサイズが大きいため、アルゴリズムは長い間追いかけていたため、速度の要件が増加しました。 私はタスク専用にジェネレーターを書くことにしました。
この投稿では、64ビットと128ビットのビットの擬似乱数を取得するための線形合同法の適用に焦点を当て、操作の原理とパラメーターの選択について説明します。
標準ライブラリのRNGを使用する負担がある場合は、非標準の要件があるか、アプリケーションで乱数を生成するプロセス全体を制御したいだけです。catへようこそ。
標準ジェネレーターでダウン！
多くの人々は、乱数生成が多くのアルゴリズムの不可欠な部分であることを知っています。 乱数は、数学と統計に加えて、コンピューターモデリング、暗号化、機械学習（人工ニューラルネットワーク）、確率的最適化（進化的計算）の方法、および他の分野の多くの問題、たとえば、美しい写真のレンダリング、エンジンの仕事、ビデオゲームロジック。
かなり一般的なプログラミング言語にはすべて、ランダムな（または、非常に正確に言えば、疑似ランダムな）数を生成する機能があります。 ただし、独自の乱数ジェネレーター（RNG）を実装することが必要になる場合があります。 「すぐに使える」RNGは通常ほとんどの場合に使用するには十分ですが、冷たすぎるジェネレーターは必要ないように思われますが、組み込みのRNGはまだ快適ではありません。
理由は異なる場合があり、一見すると明らかではありません。 まず、乱数を生成する問題には、作業の速度と結果の品質のバランスを見つけることが含まれることが多いことに注意してください。 時には、少し速くしたり、少し難しくしたりする必要があります。
第二に、RNGは単なる複雑な算術演算ではなく、厳密に決定されたアルゴリズムであり、その特性は大きく異なる場合があります。 一部の科学実験では、テスト条件を完全に記述して、確実に再現できるようにする必要があります。 これらには、RNGアルゴリズムとパラメーターが含まれます。 この場合、独自の実装を持つことをお勧めします。
異なるRNGの同時操作が必要なタスクが発生する場合があります。 それは異なり、組み込みジェネレーターは通常1つです。 もちろん、異なる初期グレインで複数のコピーを実行することもできますが、この場合、ジェネレーターは異なるシーケンスから単純に同じシーケンス（周期的に繰り返す）の要素を生成します。 サイクルの長さは膨大ですが、理論的にはこれが問題を引き起こす可能性があります。
私の場合、128ビットの数値を生成する必要がありました。 C ++では、少なくとも64ビットを返す関数はありません。 長いグーグルの後、さまざまなコンパイラ、64ビットを生成する松葉杖のセットでrand（）とRAND_MAXに混乱を見つけ、組み込みRNGを放棄することにしました。 ジェネレータを書くことは基本的なタスクのように思えました-線形合同ジェネレータの数回の反復で2つの64ビット数を取得し、それらを接着します。 それほど単純ではありませんでした。 しかし、まず最初に。
原因に！
それでは、RNGの作成を始めましょう。 基礎として、式に従って機能する単純で一般的な線形合同法を考えてみましょう。
ここで、 x i 、 x i + 1-現在および次の乱数。 a 、 c 、およびmはいくつかの定数です。 mod-除算の剰余を見つけるための演算子。
定数mは 、ソフトウェア実装での分割を避けるために、しばしば2 32または2 64に等しくなります。 結果として64ビットの剰余を取得するには、 m = 2 64を使用しました。 しかし、定数aとcはどこで取得できますか？ 次のペアがウィキペディアで見つかりました： a = 6364136223846793005およびc = 1442695040888963407。 考え直すことなく、これらのパラメーターを使用してジェネレーターを作成し、遺伝的アルゴリズムをテストし始めました。 しかし、彼はすぐにサイクルを繰り返しました。 RNGに疑念が生じました。 結果として得られる64ビットの「ランダムな」数のシーケンスの最下位ビットは、ランダムな振る舞いを示すことはありませんでした。 連続番号のいくつかの2進数の値は、モノクロ画像の形式で表示されます。
下5桁、15桁、20桁の値（ゼロからの番号付け）
約20〜24の下位バイナリビットは使用に適していません。 放電数が増加すると、そのランダム性が増加します。 したがって、1つの64ビット乱数を取得するには、線形合同ジェネレーターの2回の反復が必要です。 その結果、2つの32ビットフラグメントが連結されます。
たとえば、 java.util.Randomは同じ原理を使用しますが、 m = 2 48であるため、intおよびlongの生成時に下位16ビットのみが破棄されます。 もちろん、これは乱数の品質に悪影響を及ぼします。
図に示すように、 a = 6364136223846793005、 c = 1442695040888963407、 m = 2 64 、 x 0 = 0で取得される64ビット数のシーケンスの例を次に示します。
1442695037175000593
11166244415259155177
7076646891078057782
1459328390042580878
8905969149530007863
11682375496967736740
897247724006084730
これらの数字はどのくらいランダムですか？ 標準JavaライブラリからのRNGレベル程度で、おそらく少し良くなります。 各数の計算に必要な乗算操作は2つだけです。
複数の異なるジェネレーターが必要な場合は、 m = 2 64で計算された定数aおよびcの他の値を選択する必要があります。 ここの記事では、「良質」の3つの定数の例を示します。
| a = 2862933555777941757 |
c-奇数、 m = 2 64 |
| a = 3202034522624059733 | |
| a = 3935559000370003845 |
128ビットの乱数
2つの64ビット数値を1つに盲目的化するのに複雑なことはありませんが、興味深い点が1つあります。 「。
アイデアは、必要な4つではなく、線形合同ジェネレーターの3つの反復に対応することです。 これは、前の方法のように32ビットではなく、各反復で結果の最下位20ビットのみを破棄する場合に実現できます。 上記のモノクロ写真でわかるように、20番目のカテゴリは既に使用するのに十分なランダムです。 残りのビットを使用すると、128ビットの数値を作成できます。
コードでどのように表示されるのか不思議に思われる場合。
class RandomGenerator { public: RandomGenerator(unsigned long long int seed = 0); void next(unsigned long long int *hi, unsigned long long int * lo); private: unsigned long long int currentSeed; }; RandomGenerator::RandomGenerator(unsigned long long int seed) : currentSeed(seed) {} void RandomGenerator::next(unsigned long long int *hi, unsigned long long int *lo) { const unsigned long long int a = 6364136223846793005; const unsigned long long int c = 1442695040888963407; const unsigned long long int x = a * this->currentSeed + c; const unsigned long long int y = a * x + c; const unsigned long long int z = a * y + c; *hi = (x & 0xfffffffffff00000) | (z >> 44); *lo = (y & 0xfffffffffff00000) | ((z >> 24) & 0xfffff); this->currentSeed = z; }
同じパラメーターa 、 c 、 m 、およびx 0を使用すると、次の数値が取得されます。
26613026195691280501944396807868523054
136526799440480448897747671965175330512
26919857327062567305005081067174740455
151962490054994640693408155996993201355
16551299175504952598134597160493279376
67275013191410065527820230898073478166
72445587156806476974393951227561270647
乱数を抽出するこの方法は、アプリケーションが機能するのに十分であることが判明しました。 すぐに実用的になりました。 記事の情報はきっと役に立つでしょう。 それだけです、ご清聴ありがとうございました。 （ カバーに立方体が描かれている写真は、 ここから撮影されています 。 ）
明けましておめでとうございます！