2

ランダム化された入力でテストを実行したいので、「適切な」乱数、つまり、テストされた関数の前提条件に合格するのに十分に一致する数値を生成する必要がありますが、うまくいけば、そのコードの奥深くで大混乱を引き起こします。

math.random()（私はLuaを使用しています）均一に分散された乱数を生成します。これらをスケールアップすると、小さな数よりもはるかに多くの大きな数が得られ、整数はほとんどなくなります。

「単純な」数値を強く支持する方法で、乱数を歪めます (または、古い関数を乱数源として使用して新しい乱数を生成します) が、範囲全体をカバーします。つまり、正/負の無限大まで拡張します。 (または±1e309) double。これの意味は：

  • たとえば、10 までの数字が最も一般的です。
  • 整数は分数よりも一般的であるべきです。
  • 0.5 で終わる数字は、最も一般的な分数である必要があります。
  • 0.25 と 0.75 が続きます。次に 0.125、
  • 等々。

別の説明:確率の合計が 1 になるように基本確率xを修正し、数nの確率をx kとして定義します 。ここで、kは、nが超現実的な数1として構成される世代です。xを 0 に、x 2を -1 と +1 に、 x 3を -2、-1/2、+1/2 と +2 に、というように割り当てます。これは、私が望むものに近いものをうまく説明していますが (少し歪んでいます)、乱数の計算にはほとんど使用できません。結果の分布はどこにも連続的ではありません (フラクタルです!)。基本確率を決定する方法がわかりません。x（無限の精度ではゼロになると思います）、これに基づいた反復による数値の計算は非常に遅くなります（大きな数値を構築するのにほぼ無限の時間を費やします）。

均一に分散された乱数ソースが与えられた場合、上記のように非常に大まかに分散された乱数を生成する単純な近似を知っている人はいますか?

何千ものランダム化されたテストを実行したいのですが、品質よりも量/速度が重要です。それでも、数値が良いということは、拒否される入力が少なくなることを意味します。

Lua には JIT があるため、通常、パフォーマンスはそれほど問題になりません。ただし、ランダム性に基づくジャンプはすべての予測を破り、多くの呼び出しmath.random() も遅くなります。これは、閉じた式が反復式または再帰式よりも優れていることを意味します。

1ウィキペディアにはシュールな数に関する記事があり、素敵な写真が掲載されています。超現実的な数は、2 つの超現実的な数のペア、つまりx := {n|m}であり、その値はペアの中間の数、つまり (有限数の場合) {n|m} = (n+m)/2(有理数として) です。ペアの片側が空の場合、それは 1 ずつインクリメント (または右が空の場合はデクリメント) として解釈されます。両側が空の場合、それはゼロです。最初は数字がないので、構築できる数字は だけです0 := { | }。{0| } =: 1第 2 世代では数とを構築でき、第 3 世代では、、および(さらに既知の数のより複雑な表現、たとえば){ |0} =: -1を得ること ができます。たとえば、{1| } =: 2{|1} =: -2{0|1} =: 1/2{-1|0} =: -1/2{-1|1} ? 01/3は無限分数であるため、有限数によって生成されることはありません。同じことが浮動小数点数にも当てはまり、1/3正確に表現されることはありません。

4

3 に答える 3

1

これはアルゴリズムにとってどうですか？

  1. ライブラリ関数で (0, 1) のランダムな float を生成する
  2. 目的の確率密度関数 (たとえば、確率 0.5 で 0、確率 0.25 で 1、確率 0.125 で 2、...) に従ってランダムな整数丸め点を生成します。
  3. その丸め点でフロートを「丸め」ます (例: floor((float_val << roundoff)+0.5))
  4. 別の PDF に従ってランダムな整数指数を生成します (たとえば、それぞれ確率 0.1 で 0、1、2、3、その後減少します)。
  5. 丸められた float に 2 exponentを掛けます。
于 2012-10-07T04:03:30.600 に答える
1

シュールな 10 進展開には、ランダムな 2 進数が必要です。 偶数ビットは停止するか続行するかを示し、奇数ビットはツリーの右または左に進むかを示します。

> 0... => 0.0 [50%] Stop
> 100... => -0.5 [<12.5%] Go, Left, Stop
> 110... => 0.5 [<12.5%] Go, Right, Stop
> 11100... => 0.25 [<3.125%] Go, Right, Go, Left, Stop
> 11110... => 0.75 [<3.125%] Go, Right, Go, Right, Stop
> 1110100... => 0.125
> 1110110... => 0.375
> 1111100... => 0.625
> 1111110... => 0.875

ランダムな 2 進数をすばやく生成する 1 つの方法は、math.random() で 10 進数を調べ、0 ～ 4 を '1' に、5 ～ 9 を '1' に置き換えることです。

  • 0.8430419054348022 は 1000001010001011 になり、-0.5

  • 0.5513009827118367 は 1100001101001011 となり、0.25 etc

lua プログラミングはあまりやったことがありませんが、Javascript では次のことができます。

Math.random().toString().substring(2).split("").map(
    function(digit) { return digit >= "5" ? 1 : 0 }
);

または真のバイナリ展開:

Math.random().toString(2).substring(2)

どちらが真に「ランダム」なのかはわかりません。テストする必要があります。

この方法でシュールな数を生成できますが、ほとんどの結果は a/2^b の形式の 10 進数で、整数は比較的少なくなります。3 日目には 2 つの整数 (-3 と 3) に対して 6 つの小数が生成され、4 日目には 2 対 14 になり、n 日目には 2 対 (2^n-2) になります。

から 2 つの一様乱数を追加するmath.random()と、「三角形」のような分布 (中心から直線的に減少) を持つ新しい分布が得られます。3 つ以上追加すると、0 を中心とした分布のような「ベル カーブ」が得られます。

math.random() + math.random() + math.random()  - 1.5

乱数で割ると、真に乱数が得られます。

A/(math.random()+1e-300)

これは、A と (理論的には) A*1e+300の間の結果を返しますが、私のテストでは、結果が A と 2*A の間にある時間の 50% と、A と 4*A の間にある時間の約 75% を示しています。

それらをまとめると、次のようになります。

round(6*(math.random()+math.random()+math.random() - 1.5)/(math.random()+1e-300))

これは -9 から 9 の間の数値の 70% 以上を返し、いくつかの大きな数値がめったに現れません。

この分布の平均と合計は、大きな負または正の数に向かって発散する傾向があることに注意してください。これは、実行回数が増えるほど、分母の小さな数が数を「爆発」させる可能性が高くなるためです。 147,967 または -194,137 などの大きな数に。

サンプル コードについては、 gistを参照してください。

ジョシュ

于 2012-10-26T06:27:48.090 に答える
0

n番目に生まれたシュールな数をすぐに計算できます。

たとえば、1000 番目の超現実的な数字は次のとおりです。

  1. バイナリに変換:

    1000 dec = 1111101000 ビン

  2. 1 がプラスになり、0 がマイナスになります。

    1111101000

    +++++-+---

  3. 最初の「1」ビットは 0 の値で、次の同様の数値のセットは +1 (1 の場合) または -1 (0 の場合) であり、値はそれぞれ 1/2、1/4、1/8 などです。後続のビット。

    1 1 1 1 1 0 1 0 0 0

    + + + + + - + - - -

    0 1 1 1 1 ハァッ

    +0+1+1+1+1-1/2+1/4-1/8-1/16-1/32

    = 3+17/32

    = 113/32

    = 3.53125

この表現のビット単位のバイナリ長は、その数値が生まれた日に等しくなります。

超現実的な数の左と右の数は、末尾がそれぞれ最後の 0 または 1 に戻されたバイナリ表現です。

超現実的な数字は -1 から 1 の間で均等に分布し、特定の日に作成された数字の半分が存在します。数値の 1/4 は、-2 から -1 と 1 から 2 の間などに均等に分散して存在します。最大範囲は、指定した日数に一致する負から正の整数になります。毎日、負の範囲と正の範囲に 1 しか追加されず、最後の日よりも 2 倍の数が含まれるため、数値はゆっくりと無限大になります。

編集：

このビット表現の適切な名前は「sinary」です

負の数は転置です。元：

100010101001101s -> negative number (always start 10...)

111101010110010s -> positive number (always start 01...)

そして、すべてのビット フリップが、転置である最初のビット フリップを受け入れることに気付きます。

Nan は => 0 (他のすべての数値は 1 で始まるため) であり、先行ゼロが必要なため、コンピューターのビット レジスタでの表現に理想的です (もう 3 進コンピューターを作成していません... 残念です)。

すべてのコンウェイ超現実代数は、2 進数または 10 進数に変換する必要なく、これらの数値で実行できます。

シナリー形式は、1 に 2 の補数の 10 進数表現が付加された単純な 1 のカウンターを加えたものと見なすことができます。

これは、finary に関する不完全なレポートです (sinary に似ています): https://github.com/peawormsworth/tools/blob/master/finary/Fine%20binary.ipynb

于 2020-06-08T07:42:10.177 に答える