謎 IBL サンプラー(mythterious IBL sampler)

Importance-sampled 128 points from HDRI map. nyaxt さんと実装を競い合っている? 、とある CG 教授から教えてもらった IBL 向け謎サンプラーです。 特徴は o 実装がとても簡単 o 高速 o サンプル点の品質もそんな悪くないんじゃね？ という感じ。 やっていることは pbrt の IALSWIS [1] や VEM [2] と同じ感じ。 というか多分やりかたがちょっと違うだけで、 本質的にはやっていることはほとんど同じでしょう。 とはいえ、実際にとりあえずえいやで実装してみると、 左上ふちに集中してサンプルが生成されたりと、 (確率密度がほとんど 0 なので、サンプルしても無駄) 細かな部分でいろいろ自分の実装がわるいのかどうか原因等を調べるのが必要だったり、 サンプル分布の品質のリファレンスとして使える EIHDRI との比較はどうかなど、 いくらか調べあげないといけないことはあります。 [1] http://www.pbrt.org/plugins.php [2] http://www.mpi-inf.mpg.de/resources/hdr/vem/

一本一億円のソフトウェア

マネー革命３[1] より。 90 年代の金融の世界では、複雑化した金融商品やリスクの計算のために、 単純なブラックショールズ解析解などはもう時代遅れで、モンテカルロ法、 つまり乱数を用いてシミュレーション計算を行うことが必須となってきた時代でした。 そんなとき、モンテカルロ法によるシミュレーション計算を 10 – 100 倍に高速化する 乱数を生成するソフトが発表されました。値段はなんと一本一億円。 膨大に増え続ける計算量にコンピュータのパワーが追いつかなくなっていた頃であったそうなので、 乱数ソフトをかえるだけで計算時間が 1/10 – 1/100 になることは画期的でした。 とある邦銀では、この画期的な乱数ソフトを用いて金融計算やリスク計算の高速化を行うべく、 担当者がこの乱数ソフトの購入を重役会議にて稟議にかけました。 重役「で、その一億円もするソフトウェアとはいったい何なんだね？」 担当「はい、乱数、つまりでたらめな数字が収録されたソフトウェアです」 重役「そんなでたらめな数字を出すソフトウェアに一億円もだせるか」 めでたく稟議は棄却されましたとさ。 というような冗談のようなやりとりがあったそうです [1]。 — さて、少し考察してみたい。 このソフトがなんであるのかの詳細は [1] では結局のところ書かれていないが (リスク計算を行うソフトウェアの見本市である「Risk ’98」で発表されたソフトらしい)、 「良い乱数で計算時間が 1/10 ~ 1/100 になる」というのは、 これは間違いなく低食い違い量列(LDS)のことであろう。 LDS の研究と、LDS の金融工学への応用で有名な手塚先生によれば、氏も関連していた、 LDS を用いて(より具体的なアルゴリズムは [2] の手法だと思う)、 MBS(Morgage Backed Securities)の計算を 100 倍高速に行う FinDer と呼ばれるソフトウェア [7] には当時

Sort Benchmark

Sort Benchmark homepage http://research.microsoft.com/barc/SortBenchmark/ ソート野郎が世界最高速のソートアルゴリズムを競い合う場所。 世の中すごい野郎がいるものです。 ギガバイト単位やテラバイト単位のデータに対するソートアルゴリズム(Nsort など)はもう、 CPU のキャッシュやメモリのキャッシュやらディスクのキャッシュまで考えたソートプログラムとなっており、 純粋に最速ソートアルゴリズムというよりは最速のソートシステムという感じです。 というわけで、Bytes-Split-Index Sort (BSIS) が最速のソートアルゴリズム (アルゴリズムのオーダは O(N) らしい)のような感じがしますが、 BSIS が基本としている Self-Indexed Sort(SIS) [1] は、そのアルゴリズムはすでにあるものであり、 またテスト結果には疑問があるという意見 [2]　もありますので、少し怪しい感じがします。 Flash sort [3] も O(N) のアルゴリズムらしいですが、それと比較するとどうなのかな？ [1] A New Sort Algorithm: Self-Indexed Sort [2] Comment on Self-Indexed Sort [3] http://lucille.atso-net.jp/blog/?p=135

ハードウェア•レイトレーサーの研究開発

tueda_wolf さんの日記より。 日本の会社でハードウェアレイトレチップを開発中らしい。 http://www.euphonic-tech.com http://www.euphonic-tech.com/raytracer.html へー、どれくらいのレイトレができるんだろう。 SIGGRAPH 2005 ではレイトレプロセッサ RPU の論文が発表されていましたが、 そろそろレイトレチップがコモディティとして日の目をみる日が出てきそう？… ハードウェアレイトレでは交差判定やシェーダ云々よりも、 空間データ構造をどう持つかが重要であると思うので、 そこがどうなっているのか気になります。 テクニカルショウ ヨコハマ2007 に出展するらしいとこのことなので、 そこで詳しく聞けるかも。

効率的市場仮説 2

ユージン•ファーマの効率的市場仮説(Efficient Market Hypothesis) [1] に関係するお話を DS lite で表現すると、、、 (ニュース) DS lite は大人気、どこも品切れです！ だが、あるおもちゃ屋で DS lite が売っていました。 そこに通りすがったのが、、、 o 「ゲーマー」だったら、、、 「とりあえず買っとけ!」 (DS lite 買えてラッキー!) o 「統計学者」だったら、、、 「記録しろ！」 本当に DS lite か？もしかしたらおもちゃ屋は ワンダースワンを DS lite と偽って売りつけようとしていないか？ 100 個購入し、99 個がワンダースワンであったら、 ”あのおもちゃ屋は偽物を売っている”と主張する (統計を取るだけで、あとは満足する) o 一方「経済学者」だったら、、、 「買うな!」 DS lite は大人気でどこも品切れであるので、 DS lite が売っているはずがない。 もし本当にこのおもちゃ屋が DS lite を売っているのだとしたら、 DS lite は大人気なので既に売れているはずであるからである。

シャノンの悪魔 vs 効率的市場仮説

天才数学者はこう賭ける—誰も語らなかった株とギャンブルの話 http://www.amazon.co.jp/dp/479176305X/ 話の内容は主に、 情報理論の創始者である天才シャノン、 最適な賭けの金額を与えるケリー基準、 そのケリー基準を利用してラスベガスで勝ちまくった常勝青山ソープという人物に 関する物語である。 常勝ソープ [1] もさりとて、シャノンがいかなる天才的人物であったかを知るためだけでも、 本書は一読の価値がある。 シャノンの悪魔 本書ではひとつ面白い事例として、「シャノンの悪魔」という投資手法について述べられている。 情報理論で有名なシャノンは、株式市場にも興味を持っていた。 彼は、株価の動きはノイズであるととらえ、そこから確実に収益を得る 手法を見つけ出したという。それが「シャノンの悪魔」である。 (これは「マックスウェルの悪魔」とかけている) シャノンの悪魔とは、以下のモデルのことである。 手持ちの資本のうち、半分を株式に、半分を現金に割り当てる。 毎日正午に値洗いを行い、常に株と現金の比率が 1:1 になるように調整する。 たとえば、1,000 ドルの資本があるとすれば、 500 ドルを株式に、500 ドルを現金とする。 もし次の日、株価が二倍になったとしよう。 資本は、1,000 ドルの株式と、500 ドルの現金となっている。 ここで、配分が半分になるように調節する。 750 ドルを株式に割当て、750 ドルを現金とする。 逆に、株価が半減したとしよう。 資本は、250 ドルの株式と、500 ドルの現金となっている。 配分が半分になるように調節する。 375 ドルを株式に割当て、375 ドルを現金とする。 これを日々くりかえしていく。 株価は毎日、二倍になるか、半額になるかが 半分の確率でおこるランダムウォークモデルとする。 以下の図は、これを 360 日間シミュレーションさせた結果である。 緑が株価で、赤がシャノンの悪魔に従って投資したリターンである。 株価は最初は 1 ドルと設定した。 最初、株価は 100