none
Randomクラスについてもう少し詳しい情報は? RRS feed

  • 質問

  • 外池と申します。

     

    .Net Frameworkのドキュメントによると、Randomクラスの乱数生成は、Knuthの減算法に依っているとのことですが、Randomクラスの実装についてもう少し詳しい情報は得られないものでしょうか?

     

    減算法の一般論については、Knuthの文献やその他の資料で勉強するこができますが、Randomクラスの実装についていくつか疑問があります。

     

    1. 初期値をInteger型(符号を除けば31bit長)で与えるにもかかわらず、NextDoubleではDouble型(仮数部は52bit)で値が戻ります。内部の乱数テーブルは、一つの値あたり何bitで保持されているのか? Double型を出力する際に、どのようにbit長を調整しているのか?
    2. 基本的には同種の疑問ですが、NextByteで得られるByte列は、内部の乱数テーブルからどのように生成されているのか?

    このあたりの情報があれば、演繹的にRandomクラスの性能を推測することはある程度可能になり有用だと思うのですが・・・。

     

    さもなければ、経験的に、Randomクラスの性能を、実際に生成される乱数の統計的な検定を行ったほうがよいかな? とも思うのですが、すでに検定された結果が利用できるのであれば、ご教示頂きたく。

     

    よろしくお願いします。

     

    2007年6月8日 8:57

回答

  • 外池です。バージョン2.0のsscliも入手して調べてみたところ、モヤモヤしていたものは、スッキリとしました。Abstractさんのまとめで、よろしいのではないかと。

     

    しかし・・・、

     

    Next(minValue, maxValue)で、maxValue-minValue<=Int32.MaxValueの比較をして分岐させることの意味が、まったく理解できずにいたのですが、minValueを負の値にする可能性があったわけですね!? これは、思いもよりませんでした。

     

    と言うのも、最初の時点で内部的には31bit整数で乱数を発生させているらしい、と感触を得た時点で、すでに、Double型の仮数部を埋めるには不十分ではないか、と不満に思っていたので、さらに整数に焼きなおす際に31bitを超える範囲に拡張するようなことは、思いつきもしませんでした。

     

    一方で、

     

    SSCLIのソースコードがC#なのには驚きました。生のCかC++かと思っていて・・・、しかも、IA32アーキテクチャに特化したテクニック満載なものかと思っていたら・・・、自分があくせく苦労しているレベルとあまり変わらないことに、がっかりしたような、ホっとしたような。複雑な思いです。減算法がNumerical Recipesでは「あまりよく研究されていないので・・・、2nd Opinion的な利用方法を推奨する」となっているのに、思いっきり使っているし(速さのみ追求?)、統計的な振る舞いが怪しいとされている下位bitも利用しているし・・・。

     

    結論として、

     

    自分のアプリでは、よく素性の知れた線形合同法を用いるか、非常に性能が良いとされているMT法を用いるかしようと思います。Double型の52bit仮数部を埋めるには、MT法で32bitの整数を2つ生成して26bitずつ使うのがよろしかと。

     

    2007年6月10日 9:07

すべての返信

  • #1.1 での話。わかる範囲で。

     

    Next 系のメソッドの内部では、Sample() が呼び出されています。

    これは Double を返すため、Next() 或いは NextBytes() では、

    結果を指定された範囲の整数に変換する処理が入ります。

    だので NextDouble() は最も単純だと言えます。

     

    Sample() の具体的動作についてはよくわかりませんが、どうやら、

    1, 整数による内部的な演算で 32bit の適当な数を得る。

    2, それが負であれば、正になるように適当な調節をする(符号なし 31bit にする)。

    3, 得られた整数に対して 4.6566128752457969E-10 を掛ける。

    これにより [0, 1) の Double を得ているようです。

     

    しかし 2.0 でも同じかと言われると、ちょっと不明です。

    Knuth の方法を使っていると明記されているのは 2.0 であり、

    1.1 には記載がないため、もしかすると違っているかも知れません。

    2007年6月8日 14:40
  • 外池です。回答ありがとうございます。

     

    私もSampleメソッドのオーバーライドをしてみたところ、#2.0では、驚いたことに、Nextには反映されませんでした。これは、あきらかにドキュメントと異なった動作をしています。ので、フィードバックしておきます。

     

    もう少し詳しくしらべてみようと思います。そもそも、#1.1と#2.0で、NextDoubleで、同じ初期値を与えた場合、再現性があるんでしょうかね・・・。.Net Frameworkのバージョン間でポータブルではないことが判明すれば、それも、かなり重要な情報ですよね。

     

    また、報告します。

     

     

     

    2007年6月9日 5:02
  • 外池の自己レスです。

     

    Randomクラスから導出したクラスの関数で、SampleメソッドのOverrideが効果があるかどうかですが、調べてみたところ、以下のとおりです。

    • #1.1については、NextDouble、Next(いずれもOverloadも)、NextBytesともに、SampleメソッドのOverrideが効果があります。
    • #2.0については、NextDouble、Next(上限値)、Next(下限値、上限値)のみに効果があり、Next(引数なし)とNextBytesは効果がありませんでした。

    次に、元のRandomクラスで、同じ初期値でインスタンスを作成した場合に、#1.1と#2.0で生成される乱数列の比較ですが、NextDoubleとNextを見る限り、同じ乱数列が生成されているようです。

     

    一通り試してみた結果を、まとめてあります。

     

    http://homepage3.nifty.com/numericworld/computer/vb/dotnetmemo.htm

    2007年6月9日 12:47
  • Windows Vista SDK ?の日本語の解説では、記述が追加されていますね。

    ----

    継承元へのメモ : Random の現在の実装からクラスを派生させて Sample メソッドをオーバーライドしたときに、(maxValue - minValue) が (MaxValue / 2) の値以上である場合、オーバーライドされたメソッドによって提供される分布は、Random.NextBytes メソッド、Random.Next メソッド、または Random.Next(Int32,Int32) メソッドで使用されません。代わりに、Random により提供される一様な分布が使用されます。この動作により、Random クラスの全体的なパフォーマンスが向上します。

    ----

     

    だそうです。

    2007年6月9日 16:42
  • 外池です。

     

    情報ありがとうございます。日本語訳が変で理解できなかったのですが、英語版を見て、納得です。私なりの訳語を掲げておきます。

     

    (外池訳)継承をプログラムする場合の注意 : Random の現在の実装からクラスを派生し、Sample メソッドをオーバーライドしたときに、Random.NextBytes メソッド、Random.Next メソッド、または (maxValue - minValue) が (MaxValue / 2) の値以上の時のRandom.Next(Int32,Int32) メソッドでは、オーバーライドされたメソッドによって提供される分布は使用されません。代わりに、Random により提供される一様な分布が使用されます。この動作により、Random クラスの全体的なパフォーマンスが向上します。

     

    そうしますと・・・、Random.Next(minValue, maxValue)についても、場合によりけり、Sampleメソッドのオーバーライドの影響をうけたり、うけなかったり、ということになるわけですな。

     

    ただ、このNoteが書き加えられたことによって、同じページの内容の自己矛盾がますます顕著になっていますね。Noteの内容と、サンプルプログラムの動作結果が、一貫していません。

     


    以下、Randomクラスを継承することに関して、独言モードですが、

     

    Randomクラスを実装したプログラマ、特に、バージョン2.0で変更を加えたプログラマは、maxValue-minvValueの値がある閾値をまたいで変化したときに、がらっと分布の異なった乱数が得られるような仕様を、不自然、不都合と思わなかったんでしょうか?

     

    あと、NextBytesメソッドや、Nextメソッドが、バージョン1.1と完全に異なる実装(動作)となることを、互換性で注意すべき点としてリストアップすることから漏れてしまっていることも遺憾です。

     

    以下は、一般論の独り言。

     

    Randomクラスのドキュメントの先頭に掲げられた「乱数についての統計的な要件を満たす数値系列を生成するデバイスです。 」という説明に空虚さを感じてしまいます。

     

    NextBytesはバージョン2.0から、内部の31bit乱数の下位8bitを取り出すようになった(以前のバージョンは上位8bit)ようですが、下位bitから取り出すことによる統計的な振る舞いの悪化は検討されているんでしょうか。よほどよく工夫されたアルゴリズムでないかぎり下位bitの乱雑さは疑うべし、というのが私の理解だったのですが。Knuthの減算法について下位bitの統計的な性質を検討した例ってあるんでしょうか。

     

    まぁ・・・、私もこの辺り、イマイチ不信感があるから、他の参考資料を勉強して、自分なりのコードを書くようにしているわけですが。

    2007年6月10日 1:22
  • 結構、複雑な仕組みですね。

    しかしパフォーマンスが向上するとのことですが、どういう仕組みになっているのでしょう?

    派生クラスの Sample() を呼び出すのか、それとも自分自身の Sample() を呼び出すのか、といったことが、

    そんなにパフォーマンスに影響を与えるとは思えないのですが。……何か乱数の性質に関する問題なのかな?

    2007年6月10日 2:51
  • 単純に、メソッドの呼び出しのオーバーヘッドの問題だけだと思います。

     

    一番基になる内部の31bit整数の減算法による乱数生成ですが、バージョン1.1では外には見えなかったのですが、バージョン2.0では、Next(引数なし)メソッドそのものなんだと思います。NextBytesはNext(引数なし)の下位8bitを切り出したものになってるようです。

     

    で、Double型でサンプルするためのSampleメソッドがあって、その結果をNextDoubleメソッドで外に出す。

     

    バージョン1.1では、Next(引数なし)、Next(上限値)、Next(下限値、上限値)、NextBytes、いずれもSampleメソッドによるDouble型の乱数生成を介していたのが、

     

    バージョン2.0では、Next(引数なし)とNextBytesはSampleメソッドより上流から値をとるようにした、とのことでしょう。


     

    しかし、Next(下限値、上限値)について、maxValue-minValueがInteger.MaxValue\2以上の場合云々の説明は、イマイチよくわかりません。ためしに導出クラスを作ってイロイロ試しているのですが、特に、動作の切り替えが行われているようには見えないのですが・・・。

    2007年6月10日 3:56
  • sscli をダウンロードして bcl のソースコード(Random.cs)を確認されてはいかがでしょうか?
    ソースコードには若干ですがコメントも書かれていますので、(私には何のことかわかりませんが)何かの参考になるかもしれません。

    それとこの件ですが、半年ほど前にフィードバックにあがっているようです。
    http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=94568

    状態は「修正しない」になっていて、Next などを自分で実装して対処して欲しいそうです。

    2007年6月10日 6:57
  • 外池です。

     

    私の手元にあるsscliはsscli_20021101となっていて、おそらく、.NetFrameworkの1.0当時のものではないかと思われます。ソースを見てみたところ、完全に中身は理解できて、しかも、Knuthから直接ではなく、Numerical Recipesのプログラムがそのまま転載されているので、少々驚いています。(私がVisual Basicでやろうとしていたことと同じ)

     

    フィードバックの件も見てみましたが・・・、

     

    「修正しない」の理由は、私にはよくわかりません。ユーザーが自分でやりたいことを書け、というのは、まぁ、そのとおりだな、とも思います。

     

    後知恵で言えば、.Net Framework 2.0の時点で、Sampleメソッドより上流側で、オーバーヘッドの影響をより少なくして整数値やバイト列の乱数が欲しいのであれば、NextRawとか、NextBytesRawとか、別名のメソッドを作ればよかったのではないかと思います。

    2007年6月10日 8:12
  • ソース コードが公開されているということを今初めて知りました。

    (そうと知らずに混合モードの挙動を追跡してた……)

     

    気を取り直して(苦笑)、結局 v2.0 での Next 系メソッドの内部動作をまとめると、

    Next() ... InternalSample() を呼び出す。

    Next(Int32, Int32) ... maxValue - minValue <= Int32.MaxValue の場合 Sample() を呼び出す。

    そうでない場合、InternalSample() を 2 回呼び出す。

    Next(Int32) ... Sample() を呼び出す。

    NextDouble() ... Sample() を呼び出す。

    NextBytes() ... InternalSample() を要素の数だけ呼び出す。

     

    といったところでしょうかね。

    2007年6月10日 8:43
  • 外池です。バージョン2.0のsscliも入手して調べてみたところ、モヤモヤしていたものは、スッキリとしました。Abstractさんのまとめで、よろしいのではないかと。

     

    しかし・・・、

     

    Next(minValue, maxValue)で、maxValue-minValue<=Int32.MaxValueの比較をして分岐させることの意味が、まったく理解できずにいたのですが、minValueを負の値にする可能性があったわけですね!? これは、思いもよりませんでした。

     

    と言うのも、最初の時点で内部的には31bit整数で乱数を発生させているらしい、と感触を得た時点で、すでに、Double型の仮数部を埋めるには不十分ではないか、と不満に思っていたので、さらに整数に焼きなおす際に31bitを超える範囲に拡張するようなことは、思いつきもしませんでした。

     

    一方で、

     

    SSCLIのソースコードがC#なのには驚きました。生のCかC++かと思っていて・・・、しかも、IA32アーキテクチャに特化したテクニック満載なものかと思っていたら・・・、自分があくせく苦労しているレベルとあまり変わらないことに、がっかりしたような、ホっとしたような。複雑な思いです。減算法がNumerical Recipesでは「あまりよく研究されていないので・・・、2nd Opinion的な利用方法を推奨する」となっているのに、思いっきり使っているし(速さのみ追求?)、統計的な振る舞いが怪しいとされている下位bitも利用しているし・・・。

     

    結論として、

     

    自分のアプリでは、よく素性の知れた線形合同法を用いるか、非常に性能が良いとされているMT法を用いるかしようと思います。Double型の52bit仮数部を埋めるには、MT法で32bitの整数を2つ生成して26bitずつ使うのがよろしかと。

     

    2007年6月10日 9:07