3

phpのmt_rand（）を使用してさまざまなランダム整数を生成するプロジェクトがありますが、最近、実際のランダムビットのストリームにアクセスできるようになりました。ビットのストリームから2つの値の間のランダムな整数を取得できるmt_rand（）に似た関数を作成する方法を理解するのに問題があります。どうすればこれを達成できますか？

4

3 に答える 3

1

私はPHP_INT_SIZE * 8ビットを読み、必要な範囲で結果の数値を押しつぶします。

function squash($nr, $min, $max)
{
    return $min + $nr % ($max - $min);
}

別の方法：

function squash($nr, $min, $max)
{
    return $min + round($nr / PHP_INT_MAX * ($max - $min));
}

これは私に起こったばかりです。ランダムストリームを使用してプッシュしてみませんかmt_srand()。

function squash($nr, $min, $max)
{
    mt_srand($nr);
    return mt_rand($min, $max);
}
于 2012-06-05T12:47:43.960 に答える
1

私は方法を考え出しましたが、使用されるビットに関して最も効率的な方法かどうかはわかりません（コードはテストされておらず、理論を示しているだけです）：

function RandomInteger($min, $max)
{
    $range = ($max - $min) + 1;
    $bitsNeeded = ceil( log($range, 2) );
    $number = ReadBitsAndConvertToInteger($bitsNeeded);
    if ($number < $range)
        return $number + $min;
    else if ($number > $range)
        return RandomInteger($min, $max);
}

ご覧のとおり、関数が繰り返される可能性があります。つまり、より多くのビットが使用されるため、使用されるビットの点で最も効率的な方法かどうかはわかりません。

Pr(repeat) = (2^bitsNeeded - range) / (2^bitsNeeded)

Therefore, 0 < Pr(repeat) < 0.5

したがって、繰り返さなければならない可能性がほぼ0.5であるという最悪の場合、10回以上繰り返される必要はほとんどなく、平均は2回弱になります。明らかに、繰り返さなければならない可能性が低くなると、これらの数値は低くなります。

于 2012-06-20T07:41:01.280 に答える
1

平均して使用するランダムビット数の点で「最適」なランダム整数生成アルゴリズムについて説明します。この投稿の残りの部分では、バイアスのない独立したランダムビットを生成できる「真の」ランダムジェネレーターがあると想定します。

1976年、DEKnuthとACYaoは、ランダムビットのみを使用して特定の確率でランダム整数を生成するアルゴリズムをバイナリツリーとして表すことができることを示しました。ランダムビットは、ツリーと各リーフ（エンドポイント）をトラバースする方法を示します。結果に対応します。また、特定のアルゴリズムがこのタスクに平均して必要とするビット数の下限も示しました。この場合、整数を均一に生成するための最適なアルゴリズムは、平均して最大でビットを必要とします。この意味での最適なアルゴリズムの例はたくさんあります。それらの1つは、J。Lumbroso（2013）によるFast Dice Roller （以下に実装）であり、もう1つは、おそらく数学フォーラムで提供されているアルゴリズムです。[0, n)log2(n) + 2一方、M。O'Neillが調査したすべてのアルゴリズムは、一度にランダムビットのブロックを生成することに依存しているため、最適ではありません。

ただし、クヌースとヤオによっても示されているように、バイアスのない最適な整数ジェネレーターは、一般に、最悪の場合、永久に実行されます。二分木に戻ると、n個の結果ラベルのそれぞれが二分木に残り、[0、n）の各整数が確率1/nで発生する可能性があります。ただし、1 / nに非終了のバイナリ展開がある場合（nが2の累乗でない場合に当てはまります）、このバイナリツリーは必然的に次のいずれかになります— </ p>

  • 「無限の」深さを持っている、または
  • ツリーの最後に「拒否」の葉を含める、

いずれの場合も、平均してランダムビットをほとんど使用しない場合でも、最悪の場合、アルゴリズムは永久に実行されます。（一方、nが2の累乗の場合、最適な二分木は有限の深さを持ち、棄却ノードはありません。）Fast Dice Rollerは、「棄却」イベントを使用してバイアスがないことを確認するアルゴリズムの例です。以下のコードのコメントを参照してください。

したがって、一般に、ランダム整数ジェネレーターは、バイアスがないか一定時間（またはどちらでもない）のいずれかですが、両方ではありません。特に、バイアスを導入せずに、実行時間が無期限であるという最悪のケースを「修正」する方法はありません。たとえば、モジュロリダクション（たとえば、mt_rand() % n）は、拒否リーフがラベル付きの結果に置き換えられる二分木と同等ですが、拒否リーフよりも可能な結果が多いため、一部の結果のみが拒否リーフの代わりになり、バイアスが発生します。設定された反復回数の後で拒否を停止すると、同じ種類の二分木（および同じ種類のバイアス）が発生します。（ただし、アプリケーションによっては、このバイアスは無視できる場合があります。ランダム整数生成にはセキュリティの側面もあり、複雑すぎてこの回答では説明できません。）

ランダムビットジェネレータがあると仮定したことに注意してください。で達成できるあなたの答えの場合ReadBitsAndConvertToInteger(1)。

高速ダイスローラーの実装

以下は、FastDiceRollerのJavaScript実装です。不偏であることを保証するために、拒否イベントとループを使用することに注意してください。 ReadBitsAndConvertToInteger(1)ランダムビットジェネレーターです（たとえば、回答で使用されているように）。

function randomInt(minInclusive, maxExclusive) {
  var maxInclusive = (maxExclusive - minInclusive) - 1
  var x = 1
  var y = 0
  while(true) {
    x = x * 2
    var randomBit = ReadBitsAndConvertToInteger(1)
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
  }
}
于 2020-07-15T16:47:46.413 に答える