2

範囲 [0, 2^64) の一様に分散された乱数発生器が与えられた場合、k < 2^64 の範囲 [0, k) の乱数発生器を (GPU 上で) 効率的に構築する方法はありますか?

うまくいかない解決策:

// not uniformly distributed in [0, k)
myRand(rng, k) = rng() % k;

// way too much branching to run efficiently on a gpu
myRand(rng, k) =
    uint64_t ret;
    while((ret = rng() & (nextPow2(k)-1)) >= k);
    return ret;

// only 53 bits of random data, not 64. Also I
// have no idea how to reason about how "uniform"
// this distribution is.
myRand(doubleRng, k) =
    double r = doubleRng(); // generates a random number in [0, 1)
    return (uint64_t)floor(r*k);

差が十分に小さい場合 (たとえば、1/2^64 以内)、不均一性を妥協しても構わないと思います。

4

2 に答える 2

3

選択肢は 2 つだけです。モジュラス (または浮動小数点) を実行して不均一性を解決するか、ループでリジェクション サンプリングを実行します。第三の選択肢は本当にありません。どちらが優れているかは、アプリケーションによって異なります。

通常、kが非常に小さい場合 (たとえば、カードをシャッフルしているため、kは 100 程度)、不均一性は非常に小さいため、32 ビットでもおそらく問題ありません。64 ビットでは、数百万のオーダーのkでも、無視できるほど小さい不均一性が得られます。いいえ、1/2^64 のオーダーにはなりませんが、1/2^20 のオーダーの不均一性が目立つ現実世界のアプリケーションは想像できません。RNG ライブラリのテスト スイートを作成したとき、意図的に既知の不適切なmod実装に対して実行したところ、32 ビットでもエラーを検出するのに非常に苦労しました。

本当に完全に均一である必要がある場合は、サンプリングして拒否する必要があります. これは非常に高速に実行でき、除算をなくすこともできます (nextPow2()拒否ループの外側で計算します。これが、私がojrandlibで行っている方法です)。参考までに、次の 2 のべき乗マスクを行う最速の方法は次のとおりです。

mask = k - 1;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
mask |= mask >> 32;
于 2013-06-17T18:40:54.620 に答える