このペースで勉強していたら間に合わないな

前回のエントリーで週に１回はエントリーしたいと書いておきながら、
いきなりできていませんが、今週は３連休だったのでなんとか間に合ったと、
ゆるーく考えておきたいと個人的には思っております。


※ 個人的な備忘録のため、やぶったって誰も文句は言わないのはわかっているのですが、
　 自分で決めたことをいきなり破っているのでかなり言い訳がましくなっております。


現在１０月の目標である応用情報処理技術者試験に向けて勉強しております。
情報処理の試験勉強をしていると毎回覚えられないものに「誤差」の概念があります。

それについて結構まじめに調べたので、備忘として残しておきます。

情報処理用語としての誤差

誤差とは、論理的に正しい値との差異のこと。
wikipediaによれば、誤差の発生原因は以下の３つがあるとのこと。

（１）データを測定する際に生じる測定誤差
（２）データを計算する際に生じる計算誤差
（３）標本調査による統計誤差（標準誤差）


wikipedia:誤差


今回は主に（２）の 『データを計算する際に生じる計算誤差』が勉強の対象となります。

真の値

これはwikipedilaの真の値の部分を読めば簡単にわかるのでそのまま引用します。

測定値から誤差を無くすことは不可能である。したがってわれわれが知り得るのは常に誤差付の値でしかない。しかしながら測定すべき量には測定方法とは無関係なある定まった値があると考えるのが合理的である。この値のことを誤差理論において 真の値 とよんでいる。

誤差の評価方法

誤差の評価方法は以下の二つ。

『相対誤差』
　　⇒ 真の値との割合で評価したもの
　　⇒ 「相対誤差」＝誤差 ÷ 真の値


『絶対誤差』
　　⇒ ⇒ 真の値との差で評価したもの
　　⇒ 「絶対誤差」＝ 誤差 − 真の値

計算誤差の種類

以下の５つが対象となります。
（１）丸め誤差
（２）打ち切り誤差
（３）情報落ち
（４）桁落ち
（５）桁あふれ（オーバーフロー／アンダーフロー）


この中でも、（３）情報落ち と（４）桁落ち の区別がなんど覚えても付け焼刃のため忘れるので、
こいつを理解しようってことが今回のエントリーの動機です。

（２）打ち切り誤差

計算処理を続ければ精度がよくなるにもかかわらず、途中で計算を止めること（打ち切り）によって生じる誤差。


wikipediaの例は自分の数学レベルでは理解できなかったので、以下の例で理解。
http://lecture.ecc.u-tokyo.ac.jp/~yamaguch/johokagaku/2008/trunc2.html


要するに∞回は計算できないから妥協できるｎ回で計算を途中でやめることによって生じる誤差。
ちなみに、上記の例の「指数関数の原点の周りのテイラー展開」が何かはわからないです・・・

（３）情報落ち

コンピュータでの計算のときのように有効桁数が限られている条件下で、
絶対値の大きい数と絶対値の小さい数を加減算したとき、絶対値の小さい数が無視されてしまう現象。

これもwikipediaの例でいまいち理解できなかったので、以下の例で理解。
http://rryu.sakura.ne.jp/compfund/backnumber/compfund057.txt


要するに、加減算を行う時、ふたつの数値の指数を等しくするために、
指数の小さい方の数値の仮数を右シフトすることが問題で、
その結果として指数の小さい方の数値の下位ビットは失われてしまいます。


その下位ビットが失われたことが『情報落ち』

■ 情報落ち ■

　加減算を行う時、ふたつの数値の指数を等しくするために、指数の小さい方
の数値の仮数を右シフトします。その結果として指数の小さい方の数値の下位
ビットは失われてしまいます。もしふたつの数値の指数がかけ離れていたとし
たらどうなってしまうでしょうか。仮数の全てのビットは右シフトによって失
われてしまい、実質0を足しているのと同じ状態になります。この現象のこと
を「情報落ち」と言います。


1.00000000000000000000000×2^(+0)
+) 1.00000000000000000000000×2^(-30)
-------------------------------------

↓

1.00000000000000000000000 ×2^(+0)
+) 0.000000000000000000000000000001×2^(+0)
--------------------------------------------
1.00000000000000000000000 ×2^(+0)


　情報落ちは合計を求める時などに問題になります。たとえ小さな数値が1万
個あったとしても、それを全て大きな数値に足し合わせてしまったら、実質1
万回0を足しているようなもので、何も変わらずちっとも合計になりません。

　これを防ぐ最も簡単な方法は、小さい方から足し合わせて行くことです。合
計を求める前に数値を大きさ順に並び替えて、小さい方から順に足し合わせて
いきます。つまり、情報落ちの原因となる極端に大きさの異なる数値の加減算
を行わないように、計算順序を変えてしまうというわけです。

（４）桁落ち

値がほぼ等しく丸め誤差をもつ数値どうしの減算を行った場合、有効数字が減少すること。
絶対値がほぼ等しく符号が異なる数値どうしの加算の場合も同様。
浮動小数点数では、上位の桁がゼロになると、正規化によってそれを詰め、
以下の桁に"0" を強制的に挿入するので、下位の桁が信頼できないものになる。
特別な場合には、演算式を変形することによって、桁落ちを避けることができる。


これは上記wikipediaから引用した部分は理解できるのだが、その後の例が
いまいち理解できなかったので、以下の例で実例としては理解。
http://rryu.sakura.ne.jp/compfund/backnumber/compfund057.txt


でもまぁ。wikipdeiaにあるように、

『浮動小数点数では、上位の桁がゼロになると、正規化によってそれを詰め、以下の桁に"0" を強制的に挿入するので、下位の桁が信頼できないものになる。』

ってことですね。

■ 桁落ち ■

　今度は逆に、ほぼ等しい数値を減算すると起こるのが「桁落ち」です。
桁落ちとは、ほぼ等しい数値を減算したことにより、通常の減算よりも有効桁
数が減少することをいいます。ほぼ等しい数値というのは、上位桁は等しく下
位桁だけが異なるという状態になっています。そこで減算を行うと上位桁は相
殺され0になり、わずかな下位桁だけの差が結果に現れます。有意な数値を保
持している桁数が減るので桁落ちというわけです。


有効桁数24桁
┌────────────┐
1.11111111111111111110111×2^(+10)
+) 1.11111111111111111110001×2^(-10)
-------------------------------------
0.00000000000000000000110×2^(-10)
1.10000000000000000000000×2^(-31)
└─┘
有効桁数2桁


　そもそも有効桁数とはなんでしょうか。たとえば財布に入っている金額を訊
かれたとします。千円札1枚だけが入っているのならば、あなたは「1000円」
だと答えることができます。この場合の金額の有効桁数は4桁となります。1円
単位まで確定しているからです。

100円玉が9枚あるのは分かるが、10円玉や1円玉がたくさんあって分からない
という場合、あなたは「約1000円」と答えるでしょう。表現上の桁数は4桁あ
りますが、この場合の有効桁数は2桁です。10円や1円単位の桁が確定していな
いからです。975円が切り上げられて1000円になったのかもしれませんし、あ
るいは1018円が切り下げられて1000円になったのかもしれません。このよう
に、はっきり確定している部分の桁数が有効桁数というわけです。

　有効桁数が減少すると確実に計算精度が悪くなります。そして一度減った有
効桁数は回復することはできません。つまり減ったら減った分だけ計算精度が
悪くなっていきます。計算によって有効桁数以外の部分にも0以外の数が入る
かもしれませんが、それが正しいという保証はありません。有効桁数以上の部
分は信用できないので、精度を回復することはできないのです。

　桁落ちでもっとも大切なことは、浮動小数点数の仮数や指数のビット数にか
かわらず発生するという点です。仮数のビット長を増やしたからといって改善
するものでも無いのです。

　桁落ちを防ぐ最も確実な方法は減算を行わないことです。といってもそんな
ことは不可能なので、たとえ減算が起こるにしても、ほぼ等しい数値の減算で
はなくなるように式を変形するという方法がいくつか知られています。

（５）桁あふれ（オーバーフロー／アンダーフロー）

これは、wikipedia:算術オーバーフローをみてもまったくわからなかったので、
Ｇｏｏｇｌｅ先生にお伺いをたて調査。以下のＵＲＬのやり取りにて理解。


理解したＵＲＬ。（教えてGoo）
http://oshiete1.goo.ne.jp/qa366272.html

※ どうでもいいですが、こういうところで回答しているエライ人は、なんで回答しているのでしょうか。。。 モチベーションはなんなのかが非常に気になっている今日この頃です。ものすごく助かりるので本当にありがたいのですが。

簡単にまとめておきます。
完全に引用ですが・・・


回答（１）『概念はこうなんです。って感じですかね。』

　演算においては、ビット幅を越えて桁が溢れてしまうことをオーバーフローといい、限りなく０に近づいた小数が、精度を保てなくなる下位桁溢れをアンダーフローといいます。


回答（２）『図であらわすこうなんです。って感じですかね。』

アンダーフロー <--> 正常範囲 <--> オーバーフロー

回答（２）に関して、正負の概念をいれると、以下のような感じですね。

負のオーバーフロー <--> 正常範囲 <--> 負のアンダーフロー
正のアンダーフロー <--> 正常範囲 <--> 正のオーバーフロー

回答（２）『アンダーフローの実例はこうなんです。って感じですかね。』

アンダーフローとは少々説明が面倒なのですが、
たとえば、5桁しかない電卓に
0.0001という数値は入力できますが
0.00001という数値は入力できないですよね？
こういう状態をアンダーフローと言います。

たとえば小数点以下5桁しか想定していない状態で
1÷100000の計算をすると答えは0.00001ですよね？
小数点以下は6桁ですので、小数点以下の桁あふれ
（アンダーフローエラー）が発生します。