4

[x..y] の範囲で乱数を生成します。x と y は任意の浮動小数点数です。関数 random() を使用します。この関数は、一様に分散された P 個の数値 (「密度」と呼びます) から [0..1] の範囲のランダムな浮動小数点数を返します。一様分布を維持する必要があり、P も同様にスケーリングする必要があります。

このような問題を簡単に解決する方法はないと思います。少し簡単にするために、間隔 [-0.5 .. 0.5]、次に [0 .. 2]、次に [-2 .. 0] で、均一性と密度を維持しながら数値を生成する方法をお尋ねします。したがって、[0 .. 2] の場合、P*2 の一様分布数から乱数を生成する必要があります。

すべてのケースrandom() * (x - y) + yで密度が低いため、明らかな単純な解決策では、すべての可能な数が生成されるわけではありません。abs(x-y)>1.0多くの可能な値が見逃されます。random() は P 個の可能な数から数のみを返すことに注意してください。次に、そのような数値に Q を掛けると、Q でスケーリングされた P 個の可能な値の 1 つだけが得られますが、密度 P も Q でスケーリングする必要があります。

4

9 に答える 9

3

あなたの問題をよく理解していれば、解決策を提供します。ただし、範囲から 1 を除外します。

N = numbers_in_your_random // [0, 0.2, 0.4, 0.6, 0.8] will be 5

// This turns your random number generator to return integer values between [0..N[;
function randomInt()
{
    return random()*N;
}

// This turns the integer random number generator to return arbitrary
// integer
function getRandomInt(maxValue)
{
    if (maxValue < N)
    {
        return randomInt() % maxValue;
    }
    else
    {
        baseValue = randomInt();
        bRate = maxValue DIV N;
        bMod = maxValue % N;
        if (baseValue < bMod)
        {
            bRate++;
        }
        return N*getRandomInt(bRate) + baseValue;
    }
}

// This will return random number in range [lower, upper[ with the same density as random()
function extendedRandom(lower, upper)
{
    diff = upper - lower;
    ndiff = diff * N;
    baseValue = getRandomInt(ndiff);
    baseValue/=N;
    return lower + baseValue;
}
于 2011-11-05T10:40:52.573 に答える
2

一定の数値密度で特定の範囲内のすべての可能な浮動小数点数を本当に生成したい場合は、浮動小数点形式を考慮する必要があります。バイナリ指数の可能な値ごとに、コードの数値密度が異なります。直接生成メソッドはこれを明示的に処理する必要があり、間接生成メソッドはそれを考慮に入れる必要があります。直接法を開発します。簡単にするために、以下はIEEE 754単精度（32ビット）浮動小数点数のみを参照しています。

最も難しいケースは、ゼロを含む間隔です。その場合、正確に均等な分布を生成するには、すべての指数を最小値に加えて非正規化数まで処理する必要があります。特殊なケースとして、ゼロを+0と-0の2つのケースに分割する必要があります。

さらに、結果に細心の注意を払っている場合は、ほぼ均一な確率ですべての値にヒットすることが期待できる十分な大きさの状態空間を持つ優れた疑似乱数ジェネレーターを使用していることを確認する必要があります。rand()これにより、C/Unixおよび場合によっては*rand48()ライブラリ関数が失格になります。代わりにメルセンヌツイスターのようなものを使用する必要があります。

重要なのは、ターゲット間隔をサブ間隔に分解することです。各サブ間隔は、バイナリ指数と符号のさまざまな組み合わせでカバーされます。各サブ間隔内で、浮動小数点コードは均一に分散されます。

最初のステップは、そのサイズに比例する確率で、適切なサブインターバルを選択することです。間隔に0が含まれている場合、またはダイナミックレンジが広い場合は、使用可能な指数の全範囲までのランダムビット数が必要になる可能性があります。

特に、32ビットのIEEE-754番号の場合、256の可能な指数値があります。各指数は、最小の正規指数領域と同じサイズである非正規化の場合を除いて、次に大きい指数の半分のサイズの範囲を管理します。ゼロは最小の非正規化数と見なすことができます。上記のように、ターゲット間隔がゼロにまたがる場合、その重みが2倍になるのを避けるために、+0と-0のそれぞれの確率をおそらく半分に減らす必要があります。

選択したサブインターバルが特定の指数によって管理される領域全体をカバーする場合、必要なのは仮数をランダムビット（32ビットIEEE-754フロートの場合は23ビット）で埋めることだけです。ただし、サブインターバルが領域全体をカバーしていない場合は、そのサブインターバルのみをカバーするランダムな仮数を生成する必要があります。

最初のランダムステップと2番目のランダムステップの両方を処理する最も簡単な方法は、ターゲット間隔を丸めて、部分的にカバーされているすべての指数領域全体を含めてから、その範囲外の数値を拒否して再試行することです。これにより、単純な2の累乗の確率で指数を生成できます（たとえば、ランダムビットストリームの先行ゼロの数をカウントすることにより）。また、一部のみをカバーする仮数を生成する簡単で正確な方法を提供します。指数間隔。（これは、+ /-0の特殊なケースを処理するための良い方法でもあります。）

別の特殊なケースとして、ターゲット間隔が存在する指数領域よりもはるかに小さい非効率的な生成を回避するために、「明らかに単純な」ソリューションは、実際にはそのような間隔に対してかなり均一な数を生成します。正確に均一な分布が必要な場合は、前述の棄却法を使用してターゲット間隔外の値を削除しながら、そのサブ間隔をカバーするのに十分なランダムビットのみを使用してサブ間隔仮数を生成できます。

于 2011-11-07T23:04:02.257 に答える
1

このアプローチを検討してください。

範囲内の基本乱数ジェネレーターが[0..1] 数値の中で生成すると仮定します

0, 1/(p-1), 2/(p-1), ..., (p-2)/(p-1), (p-1)/(p-1)

ターゲット間隔の長さが1以下の場合は、を返しrandom()*(y-x) + xます。

rそれ以外の場合は、ベースRNGからの各数値をターゲット範囲の間隔にマップします。

[r*(p-1)*(y-x)/p, (r+1/(p-1))*(p-1)*(y-x)/p]

（つまり、P番号ごとに、長さのあるP間隔の1つを割り当てます(y-x)/p）

次に、その間隔で別の乱数を再帰的に生成し、それを間隔の開始に追加します。

擬似コード：

const p;

function rand(x, y)
  r = random()
  if y-x <= 1
    return x + r*(y-x)
  else
    low = r*(p-1)*(y-x)/p
    high = low + (y-x)/p
    return x + low + rand(low, high)
于 2011-11-13T21:21:52.860 に答える
1

まあ、[0..1] * 2 == [0..2]（まだ均一）

[0..1] - 0.5 == [-0.5..0.5]等

どこでそのようなインタビューを経験したのだろうか？

更新:乗算で精度が失われることを気にし始めたい場合 (これは奇妙です。なぜなら、元のタスクではそれを気にせず、「値の数」を気にするふりをしているからです)、反復を開始できます。そのためには、一様に分散されたランダムな値を返す関数がもう 1 つ必要です[0..1)— これは、表示される値をドロップすることで実行できます1.0. その後、範囲全体を、気にしない程度に十分小さい等分にスライスできます精度の低下については、ランダムに 1 つを選択し (それを行うのに十分なランダム性があります)、[0..1) 関数を使用して、最後の部分を除くすべての部分にこのバケット内の数値を選択します。

または、気にするのに十分な値をコード化する方法を考え出すことができます — そして、このコードのランダムなビットを生成するだけです。 .

于 2011-11-05T10:42:00.510 に答える
1

あなたの質問を言い換えさせてください：

を 上の離散random()一様分布を持つ乱数発生器とし[0,1)ます。によって返さDれる可能性のある値の数を とします。それぞれの値は前の値よりもrandom()正確に大きくなります。可能な各値が前の値より正確に大きくなるように、離散一様分布で1/D乱数発生器を作成します。rand(L, U)[L, U)1/D

--

いくつかの簡単なメモ。

  1. この形式の問題は、あなたが言ったように解決できません。つまり、N = 1 の場合、私たちにできることは何もありません。
  2. 0.0の可能な値の 1 つである必要はありませんrandom()。そうでない場合は、次の場合に以下のソリューションが失敗する可能性がありますU - L < 1 / D。その場合は特に気になりません。
  3. 分析が簡単になるので、すべて半開範囲を使用します。閉じた範囲を使用するのは簡単ですが、面倒です。

最後に、良いもの。ここでの重要な洞察は、結果の全体部分と小数部分を個別に選択することによって密度を維持できるということです。

random()まず、作成するのは簡単であることに注意してくださいrandomBit()。あれは、

randomBit() { return random() >= 0.5; }

次に、{0, 1, 2, ..., 2^N - 1}一様にランダムにいずれかを選択したい場合は、 を使用して簡単randomBit()に、各ビットを生成するだけです。これを呼び出しますrandom2(N)。

を使用して、次random2()のいずれかを選択できます{0, 1, 2, ..., N - 1}。

randomInt(N) { while ((val = random2(ceil(log2(N)))) >= N); return val; }

ここで、Dが既知の場合、問題は自明です。なぜなら、floor((U - L) * D)値の 1 つをランダムに一様に選択するだけに減らすことができ、それを で行うことができるからですrandomInt()。

Dしたがって、それは知られていないと仮定しましょう。[0, 2^N)それでは、まず適切な密度の範囲でランダムな値を生成する関数を作成しましょう。これは簡単です。

rand2D(N) { return random2(N) + random(); }

rand2D()連続する可能な値の差random()が正確であることが必要な場所です1/D。そうでない場合、ここで可能な値の密度は均一ではありません。

[0, V)次に、適切な密度の範囲内の値を選択する関数が必要です。これはrandomInt()上記と同様です。

randD(V) { while ((val = rand2D(ceil(log2(V)))) >= V); return val; }

そして最後に...

rand(L, U) { return L + randD(U - L); }

L / Dが整数でない場合、離散位置をオフセットした可能性がありますが、それは重要ではありません。

--

最後に、これらの関数のいくつかは決して終了しないことに気付いたかもしれません。それは本質的に要件です。たとえば、random()ランダム性が 1 ビットしかない場合があります。次に、3 つの値のいずれかを選択するように求めた場合、終了が保証されている関数を使用して一様にランダムに選択することはできません。

于 2011-11-12T09:41:07.303 に答える
0

あなたの問題を正しく理解していれば、 rand() は細かい間隔で最終的に離散的な乱数を生成するということです。そして、これに大きな (yx) を掛けると、[x,y] の範囲の浮動小数点値の多くが失われるように、これらの細かい間隔の浮動小数点値が分散されます。それでよろしいですか？

もしそうなら、Dialecticus によって既に解決策が提供されていると思います。彼が正しい理由を説明させてください。

まず、ランダムな float を生成し、それに別の浮動小数点値を追加する方法を理解しました。加算により四捨五入の誤差が生じる場合がありますが、小数点以下第2位のみとなります。より良い精度が必要な場合は、倍精度またはより細かい数値分解能を持つものを使用してください。したがって、その注意事項があれば、問題は範囲 [0,yx] で均一な密度のランダムな float を見つけることほど難しくありません。yx = z としましょう。明らかに、z は浮動小数点であるため、整数ではない可能性があります。この問題は 2 つの手順で処理します。まず、小数点の左側に乱数を生成し、次に小数点の右側に乱数を生成します。両方を均一に行うということは、それらの合計が範囲 [0,z] にも均一に分散されることを意味します。w を最大の整数 <= z とします。単純化された問題に答えるには、最初に範囲 {0,1,...,w} からランダムな整数を選択できます。次に、ステップ 2 は、単位間隔からランダムな浮動小数点数をこの乱数に追加することです。これは、おそらく大きな値で乗算されないため、数値型が持つことができるのと同じくらい細かい解像度を持っています. （理想的なランダム浮動小数点数ジェネレーターを使用していると仮定します。）

では、ランダムな整数が最大のもの (つまり w) であり、それに追加したランダムな浮動小数点数が z - w よりも大きく、乱数が許容される最大値を超えた場合はどうでしょうか? 答えは簡単です。すべてをもう一度実行して、新しい結果を確認してください。許容範囲内の数字が得られるまで繰り返します。一様に生成された乱数が、許容範囲外の場合に破棄され、再度生成されると、許容範囲内で一様に生成された乱数になることは簡単に証明できます。この重要な観察を行うと、Dialecticus がすべての基準を満たしていることがわかります。

于 2011-11-11T03:52:49.590 に答える
0

random() で乱数を生成すると、精度 (または密度など) が未知の 0 と 1 の間の浮動小数点数が得られます。

これに数値 (NUM) を掛けると、この精度は lg(NUM) (10 を基準とする対数) だけ失われます。したがって、1000 (NUM=1000) を掛けると、最後の 3 桁が失われます (lg(1000) = 3)。

3 桁が欠落しているオリジナルに小さい乱数を追加することで、これを修正できます。しかし、精度がわからないため、それらがどこにあるかを正確に判断することはできません。

2 つのシナリオを想像できます。

(X = 範囲の開始、Y = 範囲の終了)

1: 精度 (PREC、たとえば 20 桁、したがって PREC=20) を定義し、乱数を生成するのに十分であると見なすため、式は次のようになります。

( random() * (Y-X) + X ) + ( random() / 10 ^ (PREC-trunc(lg(Y-X))) )

数字付き: (X = 500、Y = 1500、PREC = 20)

( random() * (1500-500) + 500 ) + ( random() / 10 ^ (20-trunc(lg(1000))) )
( random() * 1000 + 500 ) + ( random() / 10 ^ (17) )

これにはいくつかの問題があります:

  • 2段階ランダム生成（どれくらいランダムになるの？）
  • 最初の乱数は 1 を返します -> 結果が範囲外になる可能性があります

2: 乱数で精度を推測する

乱数を生成して精度を計算するためにいくつかの試行 (例: 4) を定義し、毎回精度をカウントします。

- 0.4663164 -> PREC=7
- 0.2581916 -> PREC=7
- 0.9147385 -> PREC=7
- 0.129141  -> PREC=6 -> 7, correcting by the average of the other tries

それが私の考えです。

于 2011-11-08T13:58:59.340 に答える
0

実際の数学では、ソリューションは提供されているだけです:

return random() * (upper - lower) + lower

問題は、浮動小数点数がある場合でも、特定の解像度しかないことです。したがって、上記の関数を適用し、欠落部分にスケーリングされた別の random() 値を追加することができます。

実用的な例を作ると、私の言いたいことが明確になります。

たとえば、random() の戻り値を 0..1 から 2 桁の精度、つまり 0.XY で取得し、100 で下位、1100 で上位を取得します。

したがって、上記のアルゴリズムでは、結果として 0.XY * (1100-100) + 100 = XY0.0 + 100 が得られます。最後の桁は 0 でなければならないため、結果として 201 が表示されることはありません。

ここでの解決策は、ランダムな値を再度生成して *10 を追加することです。これにより、1 桁の精度が得られます (ここでは、指定された範囲を超えないように注意する必要があります。これは発生する可能性があります。この場合、結果を生成し、新しい番号を生成します)。

random() 関数が配信する場所の数と、最終結果にどれだけ期待するかによって、その頻度は異なります。

標準の IEEE 形式では、精度が制限されています (つまり、2 倍の 53 ビット)。したがって、この方法で数値を生成する場合、複数の追加の数値を生成する必要はありません。

ただし、新しい数を追加するときは、指定した上限を超えないように注意する必要があります。それには複数の解決策があります。まず、制限を超えた場合は、新しい番号から始めて、新しい番号を生成します (これにより分布が変わるため、カットオフなどしないでください)。

2番目の可能性は、欠落している下位ビット範囲の間隔サイズを確認し、中間値を見つけて、結果が適合することを保証する適切な値を生成することです。

于 2011-11-05T11:14:27.177 に答える
0

RNG への各呼び出しから生じるエントロピーの量を考慮する必要があります。これは、エントロピーの低いソースからエントロピーを蓄積し、最終的にエントロピーの高いラ​​ンダム値を得る方法を示す、先ほど書いた C# コードです。

using System;
using System.Collections.Generic;
using System.Security.Cryptography;

namespace SO_8019589
{
  class LowEntropyRandom
  {
    public readonly double EffectiveEntropyBits;
    public readonly int PossibleOutcomeCount;
    private readonly double interval;
    private readonly Random random = new Random();
    public LowEntropyRandom(int possibleOutcomeCount)
    {
      PossibleOutcomeCount = possibleOutcomeCount;
      EffectiveEntropyBits = Math.Log(PossibleOutcomeCount, 2);
      interval = 1.0 / PossibleOutcomeCount;
    }
    public LowEntropyRandom(int possibleOutcomeCount, int seed)
      : this(possibleOutcomeCount)
    {
      random = new Random(seed);
    }
    public int Next()
    {
      return random.Next(PossibleOutcomeCount);
    }
    public double NextDouble()
    {
      return interval * Next();
    }
  }

  class EntropyAccumulator
  {
    private List<byte> currentEntropy = new List<byte>();
    public double CurrentEntropyBits { get; private set; }
    public void Clear()
    {
      currentEntropy.Clear();
      CurrentEntropyBits = 0;
    }
    public void Add(byte[] entropy, double effectiveBits)
    {
      currentEntropy.AddRange(entropy);
      CurrentEntropyBits += effectiveBits;
    }
    public byte[] GetBytes(int count)
    {
      using (var hasher = new SHA512Managed())
      {
        count = Math.Min(count, hasher.HashSize / 8);
        var bytes = new byte[count];
        var hash = hasher.ComputeHash(currentEntropy.ToArray());
        Array.Copy(hash, bytes, count);
        return bytes;
      }
    }
    public byte[] GetPackagedEntropy()
    {
      // Returns a compact byte array that represents almost all of the entropy.
      return GetBytes((int)(CurrentEntropyBits / 8));
    }
    public double GetDouble()
    {
      // returns a uniformly distributed number on [0-1)
      return (double)BitConverter.ToUInt64(GetBytes(8), 0) / ((double)UInt64.MaxValue + 1);
    }
    public double GetInt(int maxValue)
    {
      // returns a uniformly distributed integer on [0-maxValue)
      return (int)(maxValue * GetDouble());
    }
  }

  class Program
  {
    static void Main(string[] args)
    {
      var random = new LowEntropyRandom(2);  // this only provides 1 bit of entropy per call
      var desiredEntropyBits = 64; // enough for a double
      while (true)
      {
        var adder = new EntropyAccumulator();
        while (adder.CurrentEntropyBits < desiredEntropyBits)
        {
          adder.Add(BitConverter.GetBytes(random.Next()), random.EffectiveEntropyBits);
        }
        Console.WriteLine(adder.GetDouble());
        Console.ReadLine();
      }
    }

  }
}

ここでは 512 ビットのハッシュ関数を使用しているため、これが EntropyAccumulator から取得できるエントロピーの最大量です。これは、必要に応じて修正できます。

于 2011-11-07T18:02:02.063 に答える