Island Life

2016/05/13

誤差が生じるとき

Ruiさんがおもしろい問題をtweetしてた。もすこし厳密に書き直すとこんな感じ。

IEEE単精度浮動小数点数演算で、 x + 0.25 - 0.25x - 0.25 + 0.25 と同じにならない数xを求めよ。

xをひとつだけ求めるなら簡単だけれど、xを全て求めるのは難問になると思う。

実は、浮動小数点数の誤差についてはこれまで何度もはまってきたので、このくらい簡単さ、 と思って舐めてかかったんだけど、 全部のケースを網羅するのはやっぱり難問だった。 浮動小数点数はどこまでも油断ならない。

(1) 0.25が分解能の半分に近い場合

すぐに考えつくのはこれだろう。 浮動小数点数の分解能d(ここでは隣の浮動小数点数までの距離とする)の半分より 小さな数値は足しても引いても元の数に影響を与えない。

0.25がd/2未満なら演算の順番を入れ替えても結局変わらないんじゃないか、 と思うかもしれないが、 浮動小数点数には、プラス側とマイナス側で分解能が違う場合があるのだ。 ちょうど±2^mの場合である。 2^mを境に仮数部が受け持つ範囲が一桁シフトするので、2^mより上では隣との距離が 2^(m-p) (pはhidden bitを含まない仮数部の桁数)になるけれど、2^mより下ではその半分の距離になる。

[image]

この絵は昔のを流用してるのでdoubleって書いてあるけどfloatでも同じ。

(厳密に言えば、これは±2^mの両側が正規化数の場合。非正規化数領域ではそれ以上分解能を 細かくできないので両側の分解能は同じになる。 以前これに起因するバグを踏んだ)

プラス側のdが0.5、マイナス側が0.25になるような2^mを選ぶと、

  • 2^m + 0.25 は隣の浮動小数点数2^m + 0.5とのちょうど中間に落ちるので、 デフォルトの偶数丸め規則により結果は2^mに丸められる
  • 2^m - 0.25 は浮動小数点数として正確に表現可能。

であるので、

  • 2^m + 0.25 - 0.25 だと、最初の2^m + 0.25が2^mに丸められちゃうので、 結果は2^m - 0.25の値。
  • 2^m - 0.25 + 0.25 だと、最初の2^m - 0.25は正しく計算され、 その次の+0.25も正しく計算されて、結果は 2^m。

と言う具合に差がでる。xが -(2^m) でもプラスとマイナスが逆になるだけで同じ議論。

(なお、丸め設定が切り上げの場合、2^m+0.25は2^m+0.5に切り上げられるが、そこから0.25を引いた結果も2^m+0.5に切り上げられるので、やっぱり同じにならない)

後は、こういうmは何かってことになる。IEEE単精度浮動小数点数は仮数部が23bitあるので、 []内を2進表記とすると:

    [1.00000_00000_00000_00000_000] * 2^m  が x
    [1.00000_00000_00000_00000_001] * 2^m  が x+0.5

となるような値ってことだから、0.5 * 2^23が x、つまり x = 2^22。 符号を逆にした場合も含め、このケースに該当するのは x = ±2^22。

(2) 0.25が分解能に近い場合

類似のケースとして、0.25を足すことが2のべき乗の境界をまたぐというのもある。 2^mのプラス側の分解能が0.25、マイナス側の分解能が0.125だったとしよう。 xを 2^m - 0.125 とすると、これに0.25を足したものは2^m + 0.125だが丸められて2^mとなる。 ここから0.25を引くと 2^m - 0.25 になってしまう。 減算から先にやった場合は丸めが生じない。桁を揃えて書いてみると:

    [1.00000_00000_00000_00000_000] * 2^m   が x + 0.125
    [0.00000_00000_00000_00000_0001] * 2^m  ← これが0.125 = 2^-3

なので、正負も考慮するとxは ±(2^21 - 2^-3)。

(3) 0.25を基準にしてxが分解能の半分に近い場合

0.25は

    [1.00000_00000_00000_00000_000] * 2^(-2)

である。(1)とは逆に、xが小さくて、この数値の分解能の 半分以下であった場合にも、同様の可能性が生じる。例えばxが2^-26だった場合。

    [1.00000_00000_00000_00000_000] * 2^(-2)   0.25
    [0.00000_00000_00000_00000_0001] * 2^(-2)  x

0.25+xは丸められて0.25になるが、0.25-xは有効桁数に収まる。 (わかりやすく0.25-xと表記したが、-(x-0.25)と同じなので議論に影響はない。)

このケースは少々複雑だ。xが2^-26より少しでも大きければ0.25+xは 0.25の次の浮動小数点数に近くなるため、そちらに丸められ、加算を先にやっても 減算を先にやっても結果は同じになる。

しかし、xが2^-26より少しだけ小さい場合、加算は0.25に丸められて無かったことになるが、 減算は0.25よりひとつ下の浮動小数点数に丸められる。たとえばx = 0.875*2^(-26)なら、

    [1.00000_00000_00000_00000_000] * 2^(-2)   0.25
    [0.00000_00000_00000_00000_0000111] * 2^(-2)  x

0.25+xは

    [1.00000_00000_00000_00000_0000111] * 2^(-2) 正確な結果
    [1.00000_00000_00000_00000_000] * 2^(-2)     丸め結果

だが、0.25-xは

    [0.11111_11111_11111_11111_1111001] * 2^(-2) 正確な結果
    [1.11111_11111_11111_11111_111001] * 2^(-3)  正確な結果、正規化
    [1.11111_11111_11111_11111_111] * 2^(-3)     丸め結果

となる。xが次のパターンで#にひとつでも1があれば差が生じる。

    [0.00000_00000_00000_00000_00001######...] * 2^(-2)

したがって、このケースでのxは 2^-27 < x ≦ 2^-26 、およびその符号を 反転したもの。

(4) 0.25の加算で桁数が増えて丸めを生じる場合

xの分解能が0.25に対して十分にあっても、丸めが起きてしまうケースがある。 次の例を見てみよう。

    [1.11111_11111_11111_00000_001] * 2^13  x
    [0.00000_00000_00001_00000_000] * 2^13  0.25

加算すると、次々と繰り上がりがおきて、最上桁がひとつ増え、仮数部の有効桁数を 越えてしまい、最後のビットが失われる。

    [10.00000_00000_00000_00000_001] * 2^13  x + 0.25、正確な結果
    [1.00000_00000_00000_00000_0001] * 2^14  正規化
    [1.00000_00000_00000_00000_000] * 2^14   丸め結果

0.25の減算から先にやった場合は丸めが起こらないので、結果が食い違う。

これが起きるケースはどういったパターンだろうか。

  • 0.25による加算の繰り上がりがカスケード的に最上位まで伝搬する
  • xのLSBが1であり、0.25のビットより下位桁にある

という条件を満たせば良いので、以下の23通りのパターンがあり得る。 #の部分は0でも1でも構わない。

    [1.#####_#####_#####_#####_##1] * 2^-2   x
    [1.00000_00000_00000_00000_000] * 2^-2   0.25
    
    [1.1####_#####_#####_#####_##1] * 2^-1   x
    [0.10000_00000_00000_00000_000] * 2^-1   0.25
    
    [1.11###_#####_#####_#####_##1] * 2^0    x
    [0.01000_00000_00000_00000_000] * 2^0    0.25
    
    [1.111##_#####_#####_#####_##1] * 2^1    x
    [0.00100_00000_00000_00000_000] * 2^1    0.25
    
    …
    
    [1.11111_11111_11111_11111_111] * 2^20   x
    [0.00000_00000_00000_00000_010] * 2^20   0.25

符号が逆の場合も同様。

(z) NaNはNaNにしてNaNにあらず

あと、イレギュラーな回答として「xがNaNの場合」というのもあり得る。 NaNには何を足し引きしてもNaNだが、NaNとNaNを比較すると必ず偽になるので、 プログラムコード上で数値比較していた場合は「等しくない」となる。 ただ、ビットパターンで比べれば等しいかもしれない。等しくないかもしれない (NaNを構成するビットパターンは複数あるので)。

これは問題の「同じにならない」の解釈次第である。

他にあるかな?

多分これで全部だと思うんだけど、他のパターンを見つけたら教えてください。

なお、大元のテスト課題は、答えがpow(2, n) {n > 0} のnを埋める形だったそうなので、 (1)のパターンのみ考慮すれば良かった模様。

Tag: Programming

2016/04/24

演劇の授業

本筋とは違うところに反応するけど

http://toyokeizai.net/articles/-/115149?page=4

平田[オリザ]: …演劇を学べる高校は3年前の数字で50校ほどありますが、そのうち8割を東京、神奈川、大阪、兵庫の都市部が占めています。

50校、結構あるんだなあと思った。ここでは都市部と地方の文化資本格差の話で、その文脈では「足りてない」んだけれど、それでもやってるところがあるというのは希望だなあ。

もちろん部活動としての演劇部のある高校ははるかに多いだろうし、中には顧問が熱心に指導しているところもあるだろうけれど、公演に向けての準備と、体系的な学びは違うんで、体系的に基礎を身につけた指導者が講座として教える形がもっと広まればいいなあ。

(しかし正式な科目にするとなると、文科省が指導要項作ったりすることになっちゃうんだろうか。それはちとまずい気がする。芝居の技術というのはこれをやっとけばいいってもんじゃなくて、色々な技法を体験して各人が自分に合うものを見つけるor編み出すといったものだから。指導者は複数の技法に習熟してないとならないし、それぞれの生徒に合うものを一緒に探すこともできないとならない。あらかじめカリキュラムを決めてそれを全部やらせる、という形態には合わなさそう。となるとオプション的な位置づけの方が現場の都合は良いのかもしれない。)

Tags: 芝居, 教育

2016/03/06

訛り

今のところ、自分の英語を聞いていて一番耳につく日本語訛りは二重母音が連母音になるところだなと思った。頭の中で連母音で記憶してしまっていて、気をつけないとすぐにそれが出てきちゃう。日本語での活舌練習で連母音をはっきり発音する習慣がついてるのでなお目だつのかもしれない。通じさせるだけなら曖昧になるよりは連母音でもはっきりしてる方がいいんだろうけど。矯正するには音として覚え直すしかないように思う。

母音自体も日本語訛りを感じさせるんだけど、母音って英語話者間でも結構バリエーションがあるので、何が日本語っぽいのかまだ良くわからない。各英語方言ではそれぞれシフトの方向が一貫しているから外国語っぽくならないのかな。

アクセントのクラス、LAとかにはあるんだけど、前にハワイで探したけどみつからなかったんだよなー。今ならオンラインで何かあるかなあ。

Tag: 英語

2016/02/26

Ubuntu 14.04 / HP OfficeJet Pro 8610

プリンタを新調した。

先代のHP Photosmart C6180はかれこれ7年くらい 使ってたことになる。一昨年にink system failureが頻発して、 電解コンデンサの交換で直したのだけど、 今度は色調がおかしくなり、しまいにはマゼンタ系が全滅になった。しかも黒の単色も出たり出なかったりする。他の色に混ざって黒が出てるのに。 中を見てみると黒のインクがべったりこぼれたりしているのでインク配送系の故障だろう。 検索すると自分で修理する方法がyoutubeにあがっていて便利な世の中だと思うが 手をかけている暇がない。おまけにスキャナのフィーダーも壊れて、諦めた。

新しいプリンタはOfficeJet Pro 8610にした。税込み$140。 インクで儲けるモデルとはいええらい時代だなあ。 HPのカラーレーザープリンタが$400を切っててレーザープリンタに憧れた世代として ちょっと心惹かれたんだけど、ネットのレビューで紙詰まりがすごく取りにくいという のがあったので見送った。

設定でちょっとはまったのでメモ。

  • Ubuntuのsystem-config-printerから"Add printer"で追加しようとすると、インストールの途中で固まる。psで見るとdpkgがdefunctになってる。その親のシェルを殺すとインストールが続行されるが気持ち悪い。
  • system-config-printerでデフォルトのまま選んでゆくとhpcupsドライバになるのだけど、これだとスキャナが使えない。検索すると、hplipというドライバでないと機能サポートが弱いらしい。hplipのプリンタ設定はsystem-config-printerを介さずにやった方がいいらしい(専用のセットアップツールがある)。

一旦system-config-printerで登録したプリンタエントリを削除して、以下の手順でセットアップ。参考は https://help.ubuntu.com/community/HpAllInOne

  • sudo apt-get install hplip - これは既に入ってた。
  • sudo hp-check -r とすると、足りないパッケージを指摘されるので入れた。この時点では、出力の"PERMISSION"のところに「プリンタが見つからないよ」みたいなメッセージが出てくるんだがとりあえず先に進んだ。
  • sudo hp-setupとするとGUIのウィザードが立ち上がる。だが「デバイスが見つからない」と言われて先に進めない。lsusbするとちゃんとつながってるのに。
    shiro@scherzo:~$ lsusb
    Bus 002 Device 006: ID 03f0:7112 Hewlett-Packard 
    ...
    
  • Auto discoveryではなくusbバスID:デバイスIDを 002:006 と陽に指定してもだめ。
  • sudo hp-setup -g 002:006 としてデバッグ出力を見てみると、ちゃんとUSBのデバイスからモデル名を読んでるのに、/usr/share/hplip/data/models/models.datに該当エントリが無いってことでエラーになってるようだ。
  • /usr/share/hplip/data/models/models.datを見てみるとOfficeJet Pro 8600なんちゃら、というエントリがちゃんとある。何回か試してみるに、そのエントリのヘッダが[officejet_pro_8600]となってるのが、[hp_officejet_pro_8610]で探しに行ってるため見つからない、らしい。
  • ほんとは8600と8610で違いがあるのかもしれないけど、試しに[officejet_pro_8600]の行を[hp_officejet_pro_8610]に書き換えてsudo hp-setup 002:006を実行してみると、通った!
  • ウィザードではプリンタの名前とかを設定するだけで終了。system-config-printerにもエントリが出てくるし、SimpleScanでも自動的にスキャナを認識してくれたのでこれで良しとしよう。

Tags: PC, Printer

2016/01/30

子供と読む児童文学

らむ太の学校では2〜3週間で1冊読みきるくらいのペースで課題図書が出て 毎週レポートを書いてくんだけど、定番の児童向けの本でも知らないのが 結構あって一緒に読んで楽しんでいる。(『長靴下のピッピ』とか子供の頃 翻訳で読んだのもあったけど。) 両親の離婚とか、貧富の差とか、人種差別とか、 案外シリアスなテーマも扱ってて大人でもじっくり楽しめる。 3~4年生で読んだもののうち、いくつか印象に残ったのを挙げてみる。

  • Catwings series (Ursula K. Le Guin): 空飛ぶ猫が主人公の、読みやすいファンタジー。1冊1冊が薄いので 子供も取っつき易かった模様。
  • Bunnicula (James Howe): 嵐の夜に兎が拾われてきてから、モンロー家では奇妙な現象が起こり始めた。 飼い犬と猫のペアが謎解きに挑むさまを犬の一人称で語る。 アクションとユーモアがたっぷりで笑いながら読んだ。 らむ太のお気に入り (特にステーキのくだり。ここのpunは翻訳できるのか?)。
  • Dear Mr. Henshaw (Beverly Cleary): 「作者に感想の手紙を書きましょう!」という学校の課題で主人公の少年がしぶしぶ書き始めた 手紙が、次第に自分を取り巻く環境への洞察を深める内容へと変貌してゆく。 離婚した両親への理解、引っ越した先の環境への適応など主人公の成長ぶりが 手紙と日記のみで描写されてゆく。
  • Because of Winn-Dixy (Kate DiCamillo): 母親の不在、 新しい土地。拾った犬をきっかけに主人公の少女が周囲と打ち解けてゆき、 去った母親を許し、父親の孤独を理解する。女の子が主人公だと らむ太的にはいまいちうけが悪い。いい話なのに。
  • Shiloh (Phyllis Reynolds Naylor): 山道で出会った犬は、飼い主に虐待されていた。 犬を守るためにどうすればいいか、主人公は子供なりに考えて行動し、大きな決断に直面する。 主人公は11歳から猟銃を使うって描写があってアメリカだなあと思うが (狩りをしなければ食うに困るって程度の生活なんで、必然性はある)、 話自体はとても良い。
  • James and the Giant Peach (Ronald Dahl): みなしごが巨大化した昆虫達と大きな桃に乗って冒険する話。 らむ太が一番気に入ってたのは意地悪なおばさんが桃に潰されるところ。
  • The Cricket in Times Square (George Selden): コネチカットからニューヨークの地下鉄駅に迷い込んでしまったコオロギが 鼠と猫と友達になり、意外な才能を見出される。ニューヨークの描写が ピンと来ないようだったのでWebでタイムズスクエアの写真とか見ながら読んだ。 鼠が「老後の蓄えが…」とか愚痴る部分とかはまだ良く分からないみたいだった。
  • The Cay (Theodore Tyler): 主人公の少年はヴァージニア出身の白人で、父親の仕事で オランダ領キュラソーに暮らしていたが、第二次大戦が勃発し 島がUボートに攻撃される。安全を心配した母親と一緒にアメリカに戻ろうとする途中で 船が撃沈され、少年は黒人のティモシーと猫のシチューと共に筏で漂流し、 環礁の無人島に流れ着く。二次大戦初期の勢力とか、カリブ海の地理とか、 当時の黒人と白人の間の感情とか、わりと幅広い背景知識が要るんだけど、 サバイバル冒険ものとしても手に汗握る展開で読み出すとやめられない。

今のところ個人的な一推しはThe Cayだなあ。日本でも高校生なら 読めると思うけれど、ティモシーの訛りの強い英語から元の単語を 推測するのがちょっと難しいかも。

Tag:

More entries ...