2

除算演算子を使用せずに [0,1] の範囲で一様乱数を昇順で生成できる数式またはアルゴリズムを探しています。ハードウェアに実装しているため、除算演算をスキップすることに熱心です。ありがとうございました。

4

2 に答える 2

2

数値を昇順 (または降順) に生成するということは、それらを順番に、しかし正しい分布で生成することを意味します。つまり、サイズ N のセットの最小値の分布を知る必要があり、各段階で条件付けを使用して、既に見たものに基づいて次の値を決定する必要があることを意味します。数学的には、除算を避けるという問題を除けば、これらはどちらも簡単です。

アルゴリズム を使用して、単一の一様 (0,1) 乱数 U から N 個の一様 (0,1) の最小値を生成できます。min = 1 - U**(1/N)ここで、**は累乗を示します。言い換えれば、uniform の N乗根の補数は、 [0,1] の範囲で N uniform の最小値と同じ分布を持ち、任意の間隔の長さにスケーリングできます。

条件付けの側面は基本的に、既に生成された k 値が元の間隔の一部を食い尽くしており、現在必要なのは Nk 値の最小値であり、残りの範囲にスケーリングされていることを示しています。

2 つの部分を組み合わせると、次のロジックが得られます。N 個のユニフォームの最小のものを生成し、それを残りの間隔の長さ (最初は 1) でスケーリングし、その結果を生成した最後の値にします。次に、最小の N-1 ユニフォームを生成し、残りの間隔の長さでスケーリングし、最後のものに追加して次の値を取得します。泡立て、すすぎ、繰り返し、すべてが完了するまで繰り返します。次の Ruby 実装は、これより前に N を読み込むか指定したと仮定すると、分布的に正しい結果を返します。

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** (1.0/i)))
end

しかし、除算を使用する厄介な i番目のルートがあります。ただし、事前に N がわかっている場合は、1 から N までの整数の逆数をオフラインで事前に計算してテーブルにまとめることができます。

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** inverse[i]))
end

累乗を使用せずに正しい分布動作を順番に取得する方法を知りません。それが問題である場合は、プロセスのシーケンシャルな性質または均一性の要件のいずれかをあきらめる必要があります。

于 2013-11-09T19:08:13.000 に答える
2

いわゆる「階層化サンプリング」を試すことができます。これは、範囲をビンに分割し、ビンからランダムにサンプリングすることを意味します。このようにして生成されたサンプルは、間隔全体から生成されたサンプルよりも均一です (凝集が少ない)。このため、層化サンプリングはモンテカルロ推定値の分散を減らします (それはあなたにとって重要ではないと思いますが、分散の削減方法としてこの方法が発明された理由です)。

数値を順番に生成するのは興味深い問題ですが、間隔全体で均一な分布を得るには、より多くの計算を必要とするいくつかの式を適用する必要があると思います。計算時間を最小限に抑えたい場合は、サンプルを生成してから並べ替えるよりも良いことはできないと思います。

于 2013-11-09T20:41:28.750 に答える