2016/11/20(日)kv-0.4.37

kvライブラリを久しぶりに0.4.37にアップデートしました。

今回は、double-double (dd) 関連のアップデートです。ddのsqrtが(多分)精度が上がって速くなっています。また、sqrtに無限大を入れた時にNaNになってしまっていたバグを修正しました。

そして、重大なバグ修正を含んでいます。0.4.36までは、ddを内部に持つ区間演算 interval<dd> の除算において、ある特定の条件のときに丸めの向きを間違うバグがあり、精度保証されていなかった可能性があります。interval<dd> を使って何らかの精度保証を行っている方は、速やかに0.4.37にアップデートをお願いします。近似計算としてddを使っている場合は問題ありません。

また、ddに関してはそれなりに利用者がいるにもかかわらずきちんとした形でアルゴリズムを記載していませんでした。今回、
を書きましたので、興味のある方は是非お読み下さい。

2016/10/02(日)scan2016

scan2016という、精度保証付き数値計算の研究者が一同に会する研究会に参加してきました。2年に一度の開催なのですが、2年前は学科主任だったため参加できず、今回は4年ぶりの参加です。開催場所はスウェーデンのウプサラというところで、スウェーデンNo.1の大学であるウプサラ大学を中心に発展した街だそうです。

自分が発表した内容は大体5月に この記事 に書いたもので、だいぶ忘れかけていたので何というか気合いがなかなか入らなくて大変でした。行きの飛行機の中で電源が使えたのが大助かり。stiffなODEをどう効率的に精度保証するか、というのは何年も前からこの業界の大きなテーマで、それなりに印象を残せたのではないかと勝手に考えています。

この業界は狭くて研究者の数が多くないので、朝から晩までずっと精度保証の話を聞くという機会は滅多に無く、どの話も刺激的で大変満足出来ました。(こういう機会に自分の発表だけしてさっさと遊びに行っちゃう人は何を考えてるんだろう、と毒を吐いておこう。誰が何をしようと勝手だけど、そういう人とは友達になれないなあ。)

メキシコから来た某juliaおじさんのjulia押しが強力で割と印象に残りました。C++のテンプレートのような、型に合わせて何通りもの新しい関数を自動生成する機能があるようで、うまく使えば確かに精度保証付き数値計算にフィットするかなと。

また、double-doubleの誤差評価を厳密に頑張る話もなかなか楽しそう。某Y氏が数年前にやろうとしてた気がするが、それとの関係はどうなんだろうか。

Csendesの話面白かった。やはり遅延微分方程式に手を出すべきか?

Tuckerがオーガナイザーだったせいか、ODEの話が多めでしたね。国府先生の話で出てきた宮路先生のTaylorモデルの実装とか、興味あるなあ。

2年後に東京で開催することが正式に決定したので、頑張らないと!

IMG_3466.JPG
IMG_3472.JPG
IMG_3475.JPG
IMG_3477.JPG
IMG_3711.JPG
IMG_3721.JPG
IMG_3925.JPG
IMG_4103.JPG
IMG_4104.JPG
IMG_4109.JPG
IMG_4126.JPG
IMG_4128.JPG
IMG_4133.JPG
IMG_4139.JPG
IMG_4147.JPG
IMG_4153.JPG
IMG_4154.JPG

2016/08/03(水)半精度浮動小数点数に関する思考実験

半精度浮動小数点数というものがあります。よく使われている単精度(float, 32bit)、倍精度(double, 64bit)に対して、全長16bitと単精度の半分で浮動小数点数を表現するものです。IEEE754-2008でbinary16としてフォーマットが定められています。deep learningの隆盛とともに「精度が低くてもとにかく速く」計算するニーズが高まり、GPUでハードウェアサポートされるなど、最近注目を集めています(ような気がします)。

IEEE754-2008の半精度では、16bitを符号s(1bit)+指数部e(5bit)+仮数部m(10bit)に分割しています。指数部のオフセットは15で、従って正規化数は
x = (-1)s × 1.m × 2e-15
のように、非正規化数は
x = (-1)s × 0.m × 2-14
のように実数xと対応します。

ところで、URRという浮動小数点数の表現形式をご存知でしょうか。浜田穂積先生が80年代(IEEE754制定より前!)に提案された浮動小数点数の表現形式です。詳細は
を見ていただくとして、簡単に言えば、指数部と仮数部の区切りを可変にし、1に近い数(=指数部を表現するのに必要なbit数が少ない)ときには指数部を短くして仮数部を長くして精度を稼ぎ、非常に小さい数や非常に大きい数を表現するときには仮数部の長さを犠牲にして指数部に長いbitを割り当てる、というものです。このとき、何も考えずに指数部と仮数部を結合してしまうとその区切りが分からなくなってしまいますが、そこは指数部を表現するのに「bit列の末尾が分かるような自然数の表現方法」を用いることで解決します。例えば、Eliasのガンマ符号デルタ符号といった符号化の方法がよく知られています。

さて、半精度浮動小数点数は、bit数が少ないこともあって表現できる数値の範囲が非常に狭く、簡単にアンダーフローやオーバーフローを起こしてしまいます。正の最大数は何と65504です。正の最小数は、精度を保っている正規化数で2-14≃6.1×10-5、非正規化数まで考えても2-24≃5.96×10-8にすぎません。

そこで、URR的な考え方を用いて16bit浮動小数点数を構成したらどうなるか考えてみました。URRは-infやNaNが無いなど、現代のIEEE754に慣れた我々には使いにくいところもあるので、指数部と仮数部の区切りを可変にするという思想はそのままで、適当にフォーマットを定めます。指数部は、Eliasのデルタ符号を用いることにします。デルタ符号は1,2,3,…の自然数しか表せないので、指数部とデルタ符号で表す数値を
デルタ符号12345255256508509510511
指数部0-11-22127-128-254±0±infNaN
デルタ符号の長さ13355141515151515
のように対応させることにしました。指数部の最後の3つを特殊な数に割り当てています。仮数部は、IEEE754に倣って先頭の1を格納しない「ケチ表現」にします。このフォーマットとIEEE754-2008のbinary16で、指数部と仮数部の長さの関係を表にしてみます。
提案方式の仮数部長IEEE754-2008の仮数部長
2-2541-
2-1281-
2-1272-
2-2461
2-2362
2-2263
2-1669
2-15710
2-14711
2-8711
2-7811
2-4811
2-31111
2-21111
2-11311
201511
211311
221111
231111
24811
27811
28711
214711
215711
2166-
21272-
21281-
22531-
これを見ると、1付近では仮数部が長くなり、1から離れると徐々に仮数部が短くなっていき、(精度は低いものの)小さな数から大きな数まで表現できていることが分かります。全長16bitなどという極端に厳しい場面でこそ、このようなフォーマットが生きると思うのですがいかがでしょうか。

もちろんハードウェアのサポートが無くソフトウェアエミュレーションでは速度は絶望的ですが、将来このような優れたフォーマットが気軽に使えるようになればいいなと思っています。FPGAとかで作って遊んだりできないかなあ。

2016/06/20(月)方向付き丸めクイズ

唐突ですがクイズです。a, b, c, dはIEEE 754に従う浮動小数点数とします。以下の計算をIEEE754の+∞方向への丸め(上向き丸め)で行い、計算値をx, 真値をx*とします。このとき、「必ずx ≥ x*が成立する」と言えるのはどれか。○と☓で答えて下さい。但し、計算中にゼロ除算が起きるケースは除外してよいものとします。
  1. x = a + b
  2. x = a - b
  3. x = a × b
  4. x = a / b
  5. x = (a + b) + c
  6. x = (a × b) × c
  7. x = (a - b) - c
  8. x = a - (b + c)
  9. x = -a + b
  10. x = -( (-a) + (-b) )
  11. x = a × b + c × d
  12. x = (a + b) × (c + d)
  13. x = a / (b + c)
  14. x = a - b × c
  15. x = a + (-b) × c
  16. x = sqrt(a)
  17. x = exp(a)
少し考えれば答えは分かると思いますが、これらの答えが全て○になると誤解してるのではないかという事例にたまに遭遇しますので、こういうクイズにも意味があるのではないかと思い、記事を書いてみました。

2016/05/09(月)kv-0.4.36

というわけで、予告通りkvライブラリを0.4.36にアップデートしました。

内容は前回の記事の予告通りで、maffine3を正式アルゴリズムに昇格させました。
  • maffine → 一応maffine0として残したが消滅候補
  • maffine2 → そのまま
  • maffine3 → maffineに改名
使い勝手は0.4.34以前と変わらず、単に性能がよくなっているはずです。
OK キャンセル 確認 その他