4

数学指向の Web サイトの記事でランダム ビットを効率的に使用する方法について読んだことを思い出しますが、Google で適切なキーワードを見つけて見つけることができなくなったようで、ブラウザの履歴にもありません。

domainStart問われていた問題の要点は、領域 [ , )内の乱数のシーケンスを取得し、乱数シーケンスdomainEndのビットを効率的に使用して範囲 [ rangeStart, rangeEnd) に一様に射影することでした。ドメインと範囲はどちらも整数です (より正確には、longZ ではなく s)。これを行うアルゴリズムは何ですか？

実装に関しては、次のシグネチャを持つ関数があります。

long doRead(InputStream in, long rangeStart, long rangeEnd);

in私が使用する必要がある CSPRNG (SecureRandom を介して調整されたハードウェア RNG によって供給される) に基づいています。戻り値は と の間rangeStartでなければなりませんがrangeEnd、これを明らかに実装するのは無駄です:

long doRead(InputStream in, long rangeStart, long rangeEnd) {
    long retVal = 0;
    long range = rangeEnd - rangeStart;

    // Fill until we get to range
    for (int i = 0; (1 << (8 * i)) < range; i++) {
        int in = 0;
        do {
            in = in.read();
        // but be sure we don't exceed range
        } while(retVal + (in << (8 * i)) >= range);
        retVal += in << (8 * i);
     }

    return retVal + rangeStart;
}

これは事実上 と同じ考えだと思い(rand() * (max - min)) + minますが、私たちを押しのけるビットを破棄しているだけですmax。結果を誤って低い値にバイアスするモジュロ演算子を使用するのではなく、それらのビットを破棄して再試行します。CSPRNG をヒットすると再シードがトリガーされる可能性があるため (InputStream をブロックする可能性があります)、ランダムなビットを無駄にすることは避けたいと思います。 Henry は、このコードが 0 と 257 に対して偏っていることを指摘しています。Banthar は例でそれを示します。

最初の編集: Henry は、総和が中心極限定理を呼び出すことを思い出させてくれました。その問題を回避するために、上記のコードを修正しました。

2 番目の編集: Mechanical snail は、Random.nextInt() のソースを確認することを提案しました。しばらく読んだ後、この問題は基数変換の問題に似ていることに気付きました。以下の回答を参照してください。

4

2 に答える 2

2

あなたのアルゴリズムは偏った結果を生み出します。rangeStart=0と仮定しましょうrangeEnd=257。最初のバイトが より大きい場合0、それが結果になります。の場合0、結果は確率で0または256になります。50/50そのため0、 と256は、他のどの数字よりも 2 倍少ない可能性があります。

これを確認するために簡単なテストを行いました：

p(0)=0.001945
p(1)=0.003827
p(2)=0.003818
...
p(254)=0.003941
p(255)=0.003817
p(256)=0.001955

java.util.Random.nextInt最後のバイトだけではなく、同じことをして整数を破棄する必要があると思います。

于 2013-09-22T08:25:51.433 に答える
0

Random.nextInt() のソースを読んだ後、この問題が基数変換の問題に似ていることに気付きました。

一度に 1 つのシンボルを変換するよりも、ドメインおよび範囲内の少なくとも 1 つのシンボルを表すのに十分な大きさのアキュムレータ「バッファ」を使用して、入力シンボルのブロックを一度に変換する方が効果的です。新しいコードは次のようになります。

public int[] fromStream(InputStream input, int length, int rangeLow, int rangeHigh) throws IOException {
    int[] outputBuffer = new int[length];
    // buffer is initially 0, so there is only 1 possible state it can be in
    int numStates = 1;
    long buffer = 0;
    int alphaLength = rangeLow - rangeHigh;
    // Fill outputBuffer from 0 to length
    for (int i = 0; i < length; i++) {
        // Until buffer has sufficient data filled in from input to emit one symbol in the output alphabet, fill buffer.
        fill:
        while(numStates < alphaLength) {
            // Shift buffer by 8 (*256) to mix in new data (of 8 bits)
            buffer = buffer << 8 | input.read();
            // Multiply by 256, as that's the number of states that we have possibly introduced
            numStates = numStates << 8;
        }
        // spits out least significant symbol in alphaLength
        outputBuffer[i] = (int) (rangeLow + (buffer % alphaLength));
        // We have consumed the least significant portion of the input.
        buffer = buffer / alphaLength;
        // Track the number of states we've introduced into buffer
        numStates = numStates / alphaLength;
    }
    return outputBuffer;
}

ただし、基数間の数値の変換とこの問題には根本的な違いがあります。基数を変換するには、計算を実行するのに十分な数の情報が必要だと思います。ターゲットの基数で連続して除算すると、ターゲットのアルファベットの数字を構築するために使用される剰余が得られます。この問題では、データにバイアスをかけない限り、そのすべての情報を知る必要はありません。つまり、「fill」というラベルの付いたループで行ったことを実行できます。

于 2013-09-29T00:15:58.050 に答える