- 追加された行はこの色です。
- 削除された行はこの色です。
* 浮動小数点数の表現誤差とベストな符号化 [#t6469ae8]
浮動小数点数は,情報処理の中でも重要な位置を占めるはずなのだけど,プログラマでも気にしている人は少ない.
「処理系や言語に備わっていて当たり前」の空気のような存在だからだろう.
先日,知り合いと浮動小数点数の表現方法についてチャットで話す機会があり,「空気」について改めて考えさせられた.
そのときの話をまとめてみる.
** 浮動小数点表現とは [#w996f591]
まずは,10進数での話から.
10進数での浮動小数点表現は
> p×10^q ; 1≦p<10, q は整数
と表される.p を''仮数部'',q を''指数部''と呼ぶ.
2 進数の場合は,同様に
> p×2^q ; 1≦p<2, q は整数
となる.
** 内部表現 [#w428c777]
コンピュータ内での浮動小数点数の内部表現は,単純に 2 進数の浮動小数点数を
|仮数部 m bit|指数部 n bit|
のような形に変換して保存している.
ただし,1≦p<2 という条件から,p を2進小数に展開すると
> 1.xxxxxxxx...
と,最上位桁が必ず1となる.
そこで,内部表現では,最上位の1を省略し,xxxxxxx... の部分だけを格納していることが多い.
実際の浮動小数点数の内部表現では
- 浮動小数点表現では 0 を表現できないので,特別なビット列を割り当てる
- 無限大(Inf),非数(NaN) についても特別なビット列を割り当てる
- 指数部にゲタを履かせていることもある
などの仕様が存在するが,この話はとりあえず脇に置いておく.
** 符号表 [#w9f82873]
上記の m + n ビットのビット列を1つの符号とみなせば,
|ビット列|浮動小数点数|h
|00000000| 1.00000(2) × 2^0|
|00000001| |
|...|...|
|11111111| 1.11111(2)×2^?|
のような表に展開できる.
浮動小数点数の符号化・復号化は,このような表のテーブルルックアップによっても実装できる.
ビット演算で浮動小数点数の符号化・復号化を行っているのは,アルゴリズムにより表を圧縮していると見ることもできる.
** 符号点 [#v1ea5ba6]
上記のように符号を表に展開したのち,浮動小数点数を数直線上にプロットしてみることを考えてみる.
小学校の算数の話であり,問題の質としては別に難しいことではない.
量が多いのが大変なだけである.
ので,実際にはやらずに頭の中で「やったつもり」になっておくことにする.
** 符号表現の相対誤差 [#a2f549ac]
ここで符号表現により生じる相対誤差を考えてみる.
「相対」誤差なので,
- 表現する数が大きな場合は大きな誤差を許し
- 表現する数が小さい場合は小さな誤差しか許さない
ということである.
ある数を,浮動小数点数での符号化を行おうとした場合,その数を先の数直線上にプロットし,両脇のどちらかの符号点へ「丸める」操作を行うことになる.
つまり,符号点間の距離が問題となる.
符号点間の距離が小さければ小さいほど,符号化による丸め誤差は小さくなる.
** ベストな符号点配置 [#h436dba4]
が,符号点の数は有限である.
有限の点の数で表現する数の範囲をすべてカバーしなくてはならない.
この場合,
> 表現する数のすべての区間で相対誤差が一定
に符号点をばらまくのがベストな配置である(表現する数の分布に偏りがあるときは,頻度の多い区間に符号点を細かく配置するのがベストになるが,これは考慮しない).
というわけで,数直線上で隣り合った2つの符号点の表す数 Ci, Ci+1 について
Ci
------ = e
Ci+1
と,比が定数 e で一定となるのがベストな符号点配置だと言える.
両辺の対数を取ると
Ci
log ------ = log e
Ci+1
変形して
log Ci - log (Ci+1) = log e
つまり,対数軸上(対数方眼紙の軸上や,計算尺の目盛上)で,等間隔に符号点が配置されるのがベストな符号である.
** 一般の浮動小数点表現では [#n12fb022]
一般の浮動小数点表現では,指数部の増加に対しては,確かに対数軸上に等間隔となる.
が,仮数部は線形な表現となっている.
対数軸上に符号点をプロットすると,対数方眼紙の目盛のように,桁上がりする直前で刻みが細かく,桁上がりした後で刻みが荒くなっていることになる.
この部分は「ベストな配置」から外れることになる.
** 例 [#l9fd681c]
:仮数部|16 bit
:指数部|4 bit
:表現範囲|2^0≦Ci<2^16
という浮動小数点符号を考えてみる.
この仕様,浮動小数点数側に結構有利な条件だったりはする.
符号化時に最上位桁の1を端折ることとすると,仮数部は
> 1.0000 0000 0000 0000(2) 〜 1.1111 1111 1111 1111(2)
を表していることになる.
表現による丸め誤差が最大になるのは,指数部に繰り上がった直後,つまり
> 1.0000 0000 0000 0000(2) と 1.0000 0000 0000 0001(2)
の間になる.
この2つの符号点の値の比は
1.0000 0000 0000 0000(2) 10000(16)
e = -------------------------- = ---------- = 0.999984741(10)
1.0000 0000 0000 0001(2) 10001(16)
となる.
一方,ベストな符号点配置の場合,対数軸の数直線上に等間隔に符号点を振ると,2^0 〜 2^1 の区間には
2^20 / 16 = 2^16 = 65536
個の符号点が振られる.
2^0 〜 2^1 間に 65536 個の符号点を等間隔に振ると,隣り合う符号点の比は
e = 1 / (2^(1/65536)) = 0.999989423
となる.
確かに浮動小数点数よりは精度は上がってるけど,手間を考えると微妙,なのかもしれない.
** まとめ [#f4d3301f]
浮動小数点符号化時の丸め誤差について考えてみた.
また,「ベストな符号」についても考えてみた.
「ベストな符号」は,一定ビットの符号の丸め誤差の限界を表すものである.
浮動小数点符号化と「ベストな符号」の符号点間隔を比べて見たところ,「これは」という精度上の差は見られなかった.
浮動小数点符号の設計時には「ベストな符号」の上限値は参考になるかもしれない.