呼び出すたびに 0 または 1 を返すことができる真の乱数ジェネレーター (TRNG) がある場合、2 の累乗に等しい長さの範囲内の任意の数値を生成するのは簡単です。たとえば、0 から 63 までの乱数を生成したい場合、最大値 11111 および最小値 00000 に対して TRNG を 5 回ポーリングするだけです。問題は、範囲内の数値が等しくない場合です。 2^nに。サイコロのロールをシミュレートしたいとします。1 から 6 までの範囲が必要で、重み付けは同じです。明らかに、結果を格納するには 3 ビットが必要ですが、TRNG を 3 回ポーリングすると、2 つの誤った値が導入されます。単純にそれらを無視することもできますが、そうするとサイコロの片側が振られる確率がはるかに低くなります。
私の ome の質問は、これを最も効果的に扱っています。
0 .. R - 1 の範囲の数値が必要な場合は、R が 2 n以下になるように最小の n を選択します。次に、方法を使用して 0 .. 2 n -1の範囲で乱数 r を生成します。R 以上の場合、破棄して再度生成します。この方法で生成が失敗する確率は最大で 1/2 です。平均して 2 回未満の試行で、目的の範囲内の数値を取得できます。この方法はバランスが取れており、結果のランダム性が損なわれることはありません。
あなたが観察したように、ビットを連結することにより、可能なランダム値の範囲を2のべき乗で繰り返し2倍にすることができますが、整数のビット数(ゼロなど)で開始すると、素因数以外の範囲を取得することはできません2。
いくつかの方法があります。どれも理想的ではありません:
最初のオプションは常に良い考えではありません。番号 2 と 3 はかなり一般的です。ランダムなビットが安価な場合、通常は 3 が最速のソリューションであり、頻繁に繰り返される可能性はかなり低くなります。
最後の 1 つ。[0,31] でランダムな値を構築したと仮定し、そこから結果[0,5]rを生成する必要があります。x[0,29]の値はrmod 6 を使用してバイアスなしで必要な出力にマッピングできますが、[30,31] の値はバイアスを避けるためにフロアにドロップする必要があります。
前者の場合、有効な結果が生成されますxが、さらにランダム性が残っています。範囲 [0,5]、[6,11] などの差 (この場合は 5 つの可能な値) です。rこれを使用して、生成する必要がある次のランダム値の新しい構築を開始できます。
後者の場合、何も取得できず、再試行する必要がありますが、すべてをx破棄する必要はありません。不正な範囲 [30,31] から選択された特定の値は残り、次の開始値として自由に使用できます (2 つの可能な値)。rr
その時点からのランダムな範囲は、2 の累乗である必要はありません。その時点で必要な範囲に魔法のように到達するという意味ではありませんが、捨てるものを最小限に抑えることができるということです.
を大きくすればするrほど、オーバーフローした場合により多くのビットを破棄する必要がありますが、その可能性は低くなります。1 ビットを追加するとリスクは半分になりますが、コストは直線的に増加するだけなので、r処理できる最大のものを使用するのが最善です。