10

int r();確率0.5 でゼロまたは 1 を返すバイナリ乱数ジェネレーターがあるとします。

Boost.Random を調べたところ、たとえば 32 ビットが生成され、次のような処理が行われました (疑似コード)。

x = double(rand_int32());
return min + x / (2^32) * (max - min);

私はこれについていくつかの深刻な疑問を持っています。double には 53 ビットの仮数があり、32 ビットでは、丸め誤差などの理由から、完全にランダムな仮数を適切に生成することはできません。

IEEE754 を想定して、均一に分散された、floatまたはdouble半開放範囲で を作成する高速な方法は何でしょうか? [min, max)ここでの重点は、速度ではなく、配布の正確さにあります。

正しく定義するために、正しい分布は、無限に正確な一様分布乱数ジェネレーターを使用し、各数値について最も近い IEEE754 表現に丸めた場合に得られる分布と等しくなります。[min, max)そうしないと、その数は分布にカウントされません。

PS：オープンレンジの正しい解決策にも興味があります。

4

4 に答える 4

4

私の知る限り、正しい（そしておそらく最速の）方法は、最初に64ビットの符号なし整数を作成することです。ここで、52ビットの小数ビットはランダムビットであり、指数は1023です。範囲 [1.0, 2.0) の分散ランダム値。したがって、最後のステップは、そこから 1.0 を減算することです。その結果、[0.0, 1.0) の範囲で一様に分散されたランダムな double 値が得られます。

擬似コード:

rndDouble = bitCastUInt64ToDouble (1023 << 52 | rndUInt64 & 0xffffffffffffff) - 1.0

この方法については、http: //xoroshiro.di.unimi.itで説明されています (「単位間隔で一様な double を生成する」を参照してください)。

編集: 推奨される方法は次のように変更されました: (x >> 11) * (1. / (UINT64_C(1) << 53))

詳細は上記リンクをご覧ください。

于 2016-07-17T21:02:41.787 に答える
3

これは、効率化を試みない正しいアプローチです。

bignum クラスから始めて、その bignum の合理的なラッパーを作成します。

範囲よりも「十分に大きい」範囲を生成するため、と[min, max)の丸めにより、bignum に基づいて構築された有理数で、その範囲外の浮動小数点値が生成されます。smaller_minbigger_max

ここで、範囲を真ん中で完全に 2 つの部分に細分します (これは、合理的な bignum システムがあるため可能です)。2 つのパーツのうち 1 つをランダムに選択します。

丸めた後、選択した範囲の上部と下部が (A) の外側[min, max)(同じ側にあることに気をつけてください!) になる場合は、拒否して最初からやり直します。

(B) 範囲の上限と下限が同じに丸められる場合double(またはfloat浮動小数点数を返す場合)、作業は終了し、この値を返します。

それ以外の場合 (C) この新しい、より小さな範囲で再帰します (細分化、ランダムに選択、テスト)。

この手順が停止するという保証はありません。これは、2 つの丸めdoubleの間の「エッジ」まで常にドリルダウンするか、範囲外の値を常に選択できるため[min, max)です。ただし、これが発生する確率は (停止することはありません) 0 です (適切な乱数ジェネレーターと[min, max)ゼロ以外のサイズを想定)。

これは(min, max)、または丸められた十分に太いカントール集合の数字を選ぶ場合にも機能します。正しい浮動小数点値に丸められる実数の有効な範囲の尺度がゼロではなく、その範囲がコンパクトなサポートを持っている限り、この手順を実行でき、100% の確率で終了しますが、ハード上限はありません。時間に縛られて作ることができます。

于 2013-10-03T20:51:37.687 に答える
2

ここでの問題は、IEEE754 では、表現される可能性のある double が均等に分散されていないことです。つまり、たとえば (0,1) の実数を生成するジェネレーターがあり、IEEE754 で表現可能な数値にマップすると、結果は均等に分散されません。

したがって、「均等配分」を定義する必要があります。とはいえ、IEEE754 の各数値が、IEEE754 の丸めによって定義された間隔内にある確率の単なる代表であると仮定すると、最初に均等に分散された「数値」を生成し、IEEE754 に丸める手順によって、(定義により) " IEEE754 番号の等分布」。

したがって、十分に高い精度を選択するだけで、上記の式はそのような分布に近い任意のものになると思います。問題を [0,1) 内の数値を見つけることに限定すると、これは 1 対 1 の 53 ビット整数である、非正規化された IEEE 754 数値のセットに限定することを意味します。したがって、53 ビットの 2 進乱数ジェネレーターによって仮数だけを生成することは、高速で正しいはずです。

IEEE 754 算術演算は、常に「無限精度での算術演算とその後の丸め」です。つまり、b を表す IEEE754 数値は、a b に最も近い数値です (別の言い方をすれば、a*b を無限精度で計算し、次に丸めたものと考えることができます)。 IEEE754番号を閉じます）。したがって、min + (max-min) * x (x は非正規化数) が実行可能なアプローチであると考えています。

(注: 私のコメントから明らかなように、最小値と最大値が 0,1 とは異なる場合を指していることに最初は気づきませんでした。非正規化された数値には、それらが等間隔であるというプロパティがあります。したがって、次のように等分布を取得します。 53 ビットを仮数にマッピングします. 次に、浮動小数点演算を使用できます.これは、マシンの精度まで正確であるためです. 逆マッピングを使用すると、等分布が復元されます.

この問題の別の側面については、この質問を参照してください: Scaling Int uniform random range into Double one

于 2013-10-03T19:51:45.293 に答える
1

std::uniform_real_distribution.

今年の Going Native カンファレンスで、STL による非常に優れた講演があり、可能な限り標準ディストリビューションを使用する必要がある理由が説明されています。手短に言えば、手作業で作成されたコードは、笑えるほど品質が悪い ( と考えstd::rand() % 100てください) か、より微妙な均一性の欠陥がある傾向が(std::rand() * 1.0 / RAND_MAX) * 99あります。

編集: libstdc++ の の実装を調べたところ、次のstd::uniform_real_distributionことがわかりました。

この実装では、範囲内で[dist_min, dist_max)生成された数値から単純な線形変換を使用して、範囲内の数値を生成します[0, 1)。を使用してこのソース番号を生成しますstd::generate_canonical。その実装は、ここ(ファイルの最後) にあります。整数として表され、ここでは* で示される分布の範囲がターゲット型の仮数部に収まるstd::generate_canonical回数 ( で示されるk)を決定します。次に行うことは、基本的に、仮数の のサイズのセグメントごとに 1 つの数値を生成し、算術演算を使用して、それに応じて各セグメントに入力することです。結果の値の式は、次のように表すことができます。r[0, r)r

Σ(i=0, k-1, X/(r^i))

ここでXは の確率変数です[0, r)。範囲による各除算は、それを表すために使用されるビット数 (つまりlog2(r)) によるシフトに相当するため、対応する仮数セグメントが埋められます。このようにして、ターゲット型の精度全体が使用され、結果の範囲が であるため[0, 1)、指数は0** (モジュロ バイアス) のままであり、指数。

このメソッドが暗号学的に安全であるという暗黙の了解は信頼できません (そして、 のサイズの計算でオフバイワン エラーが発生する可能性があるのではないかと疑っていますr) が、Boost 実装よりも均一性の点ではるかに信頼できると思います投稿されており、をいじるよりも間違いなくstd::rand優れています。

ブースト コードは、実際にはこのアルゴリズムの縮退ケースであることに注意してください。つまり、入力範囲がそのサイズを表すのに少なくとも 23 ビット (IEE 754 単精度) または少なくとも 52 ビットを必要とする場合k = 1、同等であることを意味します。 (倍精度)。これは、最小範囲がそれぞれ ~840 万または ~4.5e15 であることを意味します。この情報に照らして考えると、バイナリ ジェネレーターを使用している場合、Boost の実装で問題が解決するとは思えません。

libc++ の実装を簡単に見てみると、同じアルゴリズムを使用しているように見えますが、実装が少し異なります。

(*)rは、実際には入力プラス 1の範囲です。これによりmax、urng の値を有効な入力として使用できます。

(**) 厳密に言えば、エンコードされた指数は ではありません0。IEEE 754 は仮数の基数の前に暗黙の先行 1 をエンコードするためです。ただし、概念的には、これはこのアルゴリズムには関係ありません。

于 2013-10-03T22:14:11.633 に答える