2011/01/12
拡張浮動小数点数の扱い
IEEE倍精度浮動小数点数で最大の非正規化数の10進表現である 2.2250738585072011e-308 を パーズしようとすると PHPがハングする問題 についてあれこれ。
直接の原因はx86プロセッサで浮動小数点数演算が80bit拡張精度で行われることで、 似たような話についてはWiLiKi:Gauche:拡張浮動小数点演算の謎でも触れた。
これについて、「gccのバグだろ?」と主張してるblogがあった。
そこからリンクされているgccのバグレコード323はもう10年の歴史を持つ:
ここから参照されてる論文が、この問題の良いまとめになっていた。
以下私見。
なんで80bitで計算するとまずいの?
具体的な問題はいくつかの異なる要因から生じている。
- 二重丸め問題。計算の途中結果を80bitで丸め、それをさらにdouble型の変数にストアする
時に64bitで丸めると、最後に64bitで一括して丸めた場合とは異なる結果になる場合がある。
説明の簡略化のため、本来の仮数部精度を4bit、拡張精度を6bitとして例をあげてみよう。
#bは2進数を表す。
- x = #b0.111 のとき、1/x = #b1.00010001... となる。有効数字4bitで これに近いのは #b1.000 か #b1.001 でどちらかに丸めることになるが、 1/xは中間 #b1.0001よりも後者に近いので結果は #b1.001になるべき。
- ところが、コプロセッサは有効数字6bitで計算したので1/xの結果は #b1.00010となった。 これを4bitの変数に代入すると、この値はちょうど #b1.000と #b1.001の中間なので 偶数側に丸める規則を使えば #b1.000となる。
- 指数部の範囲の問題。doubleの範囲では計算の途中結果がオーバーフローしたり アンダーフローしたりするはずなのに、拡張精度では表現できる場合。 doubleで計算してれば無限大とかNaNとか0になるはずの結果が、普通の数値になる。
- ソース上で同一に見える数値が、それが置かれるレジスタによって異なる表現を持つ問題。
x/yを2箇所で計算してて、xもyも変えてなければ結果は == になると期待してしまうが、
一方が64bitに丸められてメモリにストアされ、
もう一方が80bitのレジスタに載ったままである場合、
前者を80bitに拡張して浮動小数点数ユニットで比較すると等しくならない。
- WiLiKi:Gauche:拡張浮動小数点演算の謎の、途中結果をprintfしたら 同じなのにその後の計算結果が違ってくるというのもこのカテゴリで、 printfが受け取る「途中結果」と、実際に計算に使われてる「途中結果」が ソース上では同じなのに実は違うものであることによる。
- 上のgccバグレポートにはもうちょっと深刻な例が。 この問題のせいで、(x < y && y < x) がtrueになる場合があり、 アルゴリズムが正しく動かない。
どうすれば防げるの?
上記のようにいくつかの異なる問題が混在しているので、一律にこれをやっとけば 解決という対応は難しい。
- 浮動小数点ユニットのモードレジスタを変更して仮数部を doubleの精度に制限することはできるが、指数部の範囲は拡張精度のままなので、 上記2の問題は残る。
- 変数にvolatileつけたりgccの
-ffloat-storeオプション つけるのは、変数にアサインされる時点でdoubleになることを保証するけれど、 計算の途中結果が80bitのままになることは防げない。 - 実行時に全部64bitに載ることを保証できたとしても、コンパイラは最適化の 過程でいくつかの値をコンパイル時に計算してしまうかもしれず、その計算は 拡張精度で行われるかもしれない。
- 全部long doubleで計算することにすれば予想外の結果は出ない。 long doubleの精度がアーキテクチャによって異なることと、 アプリのコードが全部自分でコントロールできない場合に難しいことが 問題になるかも。
- C99には中間結果もちゃんと64bitでやるように指示するpragmaが指定されてるけど あんまり実装されていない (少なくともDavid Monniauxの論文の時点では)。
なんでgccは直さないの?
ここはgccチームの見解じゃなくて勝手な推測だけど。
- 「中間結果も全てIEEE doubleで計算した場合に得られるはずの理論値と一致すること」と、 「ハードが持つ最大限の精度をできるだけ使って得られる値」と、どちらが「より正しい」 かはアプリケーションによる。そして、前者を保証するオーバヘッドはかなり大きい
- もっとも、x87由来の浮動小数点数ユニットを使うのをやめて、SSEの方を使えば 64bitのまま計算できる。歴史的にみると、ハードウェア浮動小数点数ユニットが コプロセッサとして実現されだした頃 (8087とか、68881とか) は、精度について 「大は小を兼ねる」と思われていた節がある。 次第に、一貫した精度で計算することが重要ってことがわかってきて、 浮動小数点数ユニットはそういうモードを備えるようになってきた。 それならx87のフェードアウトを待つってことでもいいんじゃないか。
浮動小数点数演算てそもそも不正確なものでしょ。こまけぇことはいいんだよ
浮動小数点数演算でも、特定の条件のもとでは正確な値が計算できるし、 どうなったらどのくらい精度が失われるかも評価できる。なので、 「不正確だから」で考えを止めてしまうのはあんまり良くない。
この80bit問題の根っこは、浮動小数点数が不正確だからということよりも、 浮動小数点数演算に使われる精度をプログラマが完全に制御できない、 あるいはプログラマの直感と違う精度が使われる、というところにあると思う。
良くあるmyth:
- 「浮動小数点数演算は常に誤差を持つ」: 結果が53bitに収まる整数演算(加減乗算、 および余りの出ない除算)とか、指数部が溢れない範囲での2^n でのスケーリングとかは 誤差なくできる。
- 「浮動小数点数演算を10進数で読み書きすると不正確」:
任意の10進小数を有限桁数の2進小数に変換することはできない、という意味では
そうなんだけど。2進浮動小数点数を、「実数全体を有限個の区間に分割し、
それぞれを代表値で表現することにしたもの」と考えた場合、
ある区間内の10進小数は、常にその代表値である2進浮動小数点数表現へと
変換でき、また2進浮動小数点数表現は、常にその区間内の10進小数表現へと
変換できる。実数の各区間に対して曖昧さなく2進浮動小数点数を1対1対応
させられるってこと。
ただ、それはちゃんとアルゴリズムを実装しないとだめ。Cのprintfとか strtodはちゃんとしてない。
Tag: Programming
2011/01/08
仕上げのモチベーション
ものをつくるときって、完成に近づくにつれ、完成度を少し上げるのに 要する労力が指数的に増えて行く感じがする。 d(完成度)/d(労力) ∝ 1 - (完成度) って感じ。
だいたい何でも、完成度4〜5割で全体が見えてきたあたりから完成度8割くらいの ところまで持ってゆく時が一番手応えがあって楽しい。手を入れる度に 良くなってゆくのがわかるから。 完成度8〜9割のあたりで、だんだん楽しさよりも使命感というかプライドというか、 明らかに未完成なものを出したくないよな、っていう想いの方が支配的になってくる。 9割とか9割5分を過ぎるとむしろ執念。
でも、この最後の1割を追い込むかどうかで、出来上がりの持つ存在感というか 重みというか、が違ってくる。100%の仕事というのはなかなか出来るものではないけど、 (そもそも上の微分方程式の解は (完成度) = 1 - C・exp(-(労力)) なので 完成度を1にするには無限大の労力が必要になる)、90%で止めとくのと、97%までやる、の 違いは、例えばぱっと見で「お」と思ってもらえるかどうか、とか、 ざっと見た時に興をそぐような瑕疵がない、とか、 使い込んでも脆さを露呈しない、とか、色々なところに現れてくるような気がする。
もちろん仕事でやる場合は常にコストとの見合いだから「やりすぎ」に 気をつける必要があって、最後の方は完成度をちょっと上げるだけでコストが 跳ね上がるから何をどこまでやるかの見極めは重要なんだけど。
ただ、この9割過ぎてからの作業って、モチベーション保つのがしんどいんだよね。 文章ならもう内容はすっかり頭に入ってる(つもり)のものを何度も読み直すとか、 演奏や演技ならひととおり通して出来るようになってるものを客観的に分析して 何が足りないか探すとか、 プログラムなら既に動いてテストも通ってるんだけど抜けてるエッジケースが 無いか今一度確認するとか。
秀でる人っていうのはこの9割から先の作業を嬉々としてこなせてしまう人なのかも しれないけれど。なかなかそういうふうにはいかない。飽きがきちゃうんだよね。 ずーっと同じものを眺めつづけることになるから。依頼された原稿とか、 一度入稿したらもう見るのもうんざりだもの。
ただ、そこを楽にするコツはあるかもしれない。アプローチを変えることで、 繰り返し作業になるのを避けるのだ。
ちょうど先ほど、Gaucheのマニュアルの英文しかないところに和文をつけてたんだけど、 和文を改めて考えることで、英文で足りなかったところとか、さらにはAPI自体の不足が 見えてくる。APIだけを何度も検討したり、英文マニュアルだけ何度も推敲するのは しんどいけど、和文という別の角度からのアプローチをつけると、それ自体は新鮮な 作業なので飽きがこない。
ピアノでも、最近完成度をもうちょっと上げたいなと思うようになったんだけど、 なんとなく弾けるようになってから先がやっぱりつらい。 裏拍の練習とか、 リズム変奏してみるとか、何か変えてみると新鮮で、新しい発見があったりする。
演技においては、何十回と繰り替えしリハーサルしたシーンを、 毎回「初めて経験するように」演技しなくてはならない。 これは未だに難しくて、良く使っていたのは本番の前に毎回新しいネタで集中するとか 新しい設定を持ち込むとか、そのくらい。マイズナーテクニックをきちんと使えるように なると打破できるんじゃないかという気がする。
こういったブログの文章なんかは5割くらいの完成度で投げっぱなしに してしまうので楽なものだ。ブログをいくら書いても文章の練習にならないと 思うのはそのためだ。(毎エントリがっつり練って校正するなら別だけど、 それはもはやエッセイ集だな。)
Tags: ものつくり, Programming, Piano, 芝居
2011/01/05
さらばCRT
14年前、最初にこちらでデスクトップを組み立てた時に買ったCRTモニタ、 SonyのMultiscan 200sf (17インチ)。以来、PC本体は代替わりしても 使いつづけ、私がLCDモニタをメインにしてからはかみさん用のモニタとして 活躍してきたのだけど、昨年から時々、パワーセーブモードから復帰せずに 暗いままになったり、青の出力が落ちて画面が黄色っぽくなったり、 画面が小刻みに揺れたりする症状が出てきたので、いよいよ引退させることにした。 後継はnewegg.comで買った19" のLCD。
確か200sfは$700以上したはずで24"のLCDが$200台で買える今となっては 隔世の感があるけど、長持ちという点ではこれだけ使いつづけた PC関連装置というのは他に無いからコストパフォーマンスは非常に良かったと 言えるかもなあ。 LCD使い始めたのは2002年頃からで、確か2台はもうだめにしてる (バックライトが点灯しなくなった)。
一番最初に買ったモニタは手作りCP/Mマシン用のグリーンモニタで、 あの頃400ライン出るやつは新品で数万円したんだけど 中古で1万円のを秋葉で見つけて電車でえっちらおっちら運んだなあ。 あれも日本出るときまで使ったから10年近く持ったんじゃなかろうか。
Tag: PC
2011/01/02
仕事始め準備
USは明日月曜から通常操業なんだが、「新年明けには…」でクリスマスに突入したもろもろの課題が夏休み最終日の宿題状態であって、この点では30年くらい成長してないな。一個ずるずると引っかかると他のタスクが全部後回しになっちゃうのが問題なんだけど、かといってやりやすいタスクから手をつけていると「重い」タスクがどんどん遅延し、休暇はそういう重いタスクをえいやっと片付ける貴重な機会なので悩ましい。つか本来は休暇の前に「軽い」タスクのキューをクリアしとくべきなんだな。
とかいいつつも新年早々気を散らしていたことメモ:
The long story of long s
Hacker News経由で知ったこの記事は面白かった。
「長いs」"ſ" は、ドイツ語のßの合字の片割れ、程度にしか知識が無かったんだけど、 他のヨーロッパ言語でも広く使われてたのは知らなかった。 それも、18世紀後半にうわっと流行って、19世紀はじめに突如として 流行らなくなった、とか。
逆にドイツ語で生き残ったのは何故かってのも知りたいな。
どうしてみんなせんそうするの?
らむ太の難しい質問今年一発目。 Siggraph 2010のVideo Review DVDに入ってた、 ポーランドの歴史を8分半にまとめたアニメーションを観てたら。 (YouTubeにも上がってる。上海万博向けに作られたものらしい: http://www.youtube.com/watch?v=qr6Q0BpmyG0 )
確かにこれを見てると、戦争して街を作ってまた戦争してまた街を作って…の繰り返しだな。人類の歴史は。
ついでに、昨年締めのらむ太の難しい質問は「どうしててをはなすとものはしたにいくの?」だった (「地球が引っ張ってるからだよ」→「でもおちないものもあるよ」→以下個別事例についての質問が続く)。
Tag: 生活
2010/12/31
行く年
今年もむちゃくちゃ速かった。WiLiKiを改造してblog化したのもベイエリアに出張したのもついこないだのようだ。だが思い返してみたら「ついこないだ」やったことはたくさんあるので、単に時間的距離感覚が鈍ってきただけかもしれない。
子供も、毎日見てると変わらないような気になるけど、一年前のことを思うと成長してるなあ。プレスクールでは片言だけど英語を話しているらしい。でも映画のDVDは、単に映像を見るだけじゃなくて台詞を理解したいと思うようになってきたせいか、日本語で観たがる。
仕事ではCommon Lispばかり書いてた。もっとSchemeを書きたい。同じじゃん、と突っ込まれそうだけど。ビジネス的には今年も横這い。経済状況を考えるとラッキーか。あと訳書一つ出たのも今年だ。
Gauche 0.9を出した時にもっと高頻度にリリースを出すぞと思ったんだが、0.9.1_pre1になってから停滞して結局0.9.1まで1年開いてしまった。これはまずかった。
仕事がかなり忙しかったので芝居関係はスロー。9月にMai Poina Tourをやったのと、UHフィルムスクールの学生映画にちょっと出たのくらい。あとはScott Rogersのマイズナーのクラスを取った。ああ、Hawaii 5-Oのエキストラを一回やったか。
7-8年前に思い立った、ショパン練習曲Op10&25を全部弾いてみる、という目標は達成できた。最初は死ぬまでに弾けたらなあ程度に考えていたけど、続けてれば何とかなるものだな。
さて外の花火が騒がしくなってきた。
Tag: 生活
Comments (0)