c-lang:計算誤差
数
我々は、物を数える時、「ひとつ」「ふたつ」「みっつ」・・・と数える。
また、何かを識別するために、番号を付ける。
このように、我々の生活の中で、特に自然に用いられる1、2、3、・・・といった数字を自然数という。
何もない状態を0（ゼロ）という。
この時、足りない分は、記号「－」をつけて、－1、－2、－3・・・と表す。
これを負数といい、自然数、0、負数を合わせて整数という。
除算を行った際、例えば5÷2等、整数で表せないこともしばしばある。
この場合、2.5と表し、これを小数と言う。
0.1、0.01も小数である。
負数の小数もある。
小数とは、狭義には－1より大きく、1より小さい数を言うので、小数点記号を境に、例えば4.17の場合、4を整数部、17を小数部という。
また、5÷3の商は1.6666666・・・と、6が無限に続く小数となり、これを循環小数という。
有限の小数、若しくは循環小数は、必ず分数の形で表すことができる。 これらを総称して有理数という。
これに対し、円周率や、2の平方根等、分数の形で表せない小数もある。
これを無理数といい、有理数、無理数を総称して実数という。
コンピュータで扱える数値
ところで、循環小数や無理数など、数学の世界では「無限」を扱うことがしばしばある。
殊にＣＡＤやＧＩＳといった分野では幾何学が必須となり、必然的に円周率や平方根等を取り扱う機会が多くなる。
ところが、コンピュータは、そのような「無限」のものを扱うことはできず、有限の離散的な数値で表さざるを得ない。
コンピュータ内で、「無限」のものを「有限」の数値で表した数を近似値といい、机上に於ける実際の値を真値という。
真値と近似値の差を誤差（絶対誤差とも言う）といい、誤差の絶対値を、絶対値誤差という。
また、誤差と真値の比を相対誤差という。
例）円周率
真値：3.14159265358979323846264338327950288・・・
近似値：3.14
絶対誤差：0.00159265358979323846264338327950288・・・
相対誤差：0.0005069573829・・・
我々は、循環小数や無理数等の真値を知ることはできない。 また、一般的に真値は未知数である。
その為、システムを構築する際、予め誤差限界を見積もっておかなければならない。
誤差限界とは、許される誤差を言う。
実数
実数には、内部表現の違いで次のものがある：
float型
単精度実数（single precision real number） 1つの数値を32ビットで表現する浮動小数点数のこと。
1ビットの符号部、7ビットの指数部、24ビットの仮数部の計32ビットで表現する。
表現できる値の範囲は-3.40282×1038～3.40282×1038で、精度は6桁である。
double型
倍精度実数 (double precision real number) 1つの数値を64ビットで表現する浮動小数点数のこと。
1ビットの符号部、11ビットの指数部、52ビットの仮数部の計64ビットで表現する。
-1.79769×10308～1.79769×10308で、精度は15桁である。
精度
計算を行う際、精度を常に考慮しなければならない。
精度とは、近似値と真値が一致する桁数を表すが、厳密には、相対誤差の絶対値の逆数を言い、桁数で表す場合、10を底とした対数を取る。
浮動小数点表現(floating point representation)あるいは、科学的表記法 （scientific notation）
コンピュータが数値を扱うときの表現手法の一つ。
数値を、各桁の値の並びである「仮数部」と、小数点の位置を表わす「指数部」で表現する方法。
仮数部に、底を指数でべき乗した値をかけて実数を表現する。
表現できる数値の範囲が広いため、科学技術計算等に向いている。
小数点に関する処理が必要になるため、特定の位置に小数点を固定している固定小数点数に比べると、計算速度は遅い。 表現できる数値の幅に応じて、単精度実数や倍精度実数などの種類がある。
整数の内部表現に関しては、ほとんどの機種で同一の表現となっているのに対して、実数型に関してはいくつかの規格が存在する。
ほとんどのメインフレーム系の計算機で使用されている実数表現は IBM形式 と呼ばれるものである。 これに対して、UNIXなどのコンパイラでは IEEE（アイ・トリプル・イーと読む）規格を採用しているものが多い。
どちらも、32ビットを1語とする点は同じであるが、採用されている進法が異なり、表現できる実数の範囲や精度に違いがある。
N = M × BE または（ N = M * B^E）
M
仮数
B
基数
E
指数
IEEE規格の浮動小数点表現
符号ビット
正を0、負を1で表す。float 、doubleどちらとも1ビットを使う。
指数部
指数に127（2進数1111111）を加えるバイアス方式。
float では 7ビット、doubleでは 11ビット。
指数部は e+NN の形式で，仮数部 × 10{NN} を意味する（e の代わりに E が使われることもある）。
実際の指数に127を足すことで負数も表現できる。
仮数部
仮数を1の位の1を取り除いたかたちで左づめに数値を入れる。
余ったビットはすべて0で埋める。
float では 24ビット、doubleでは 52ビット。
有効桁数を n 桁とすると，0.1 ≦ X ＜ 10{n+1} までの値は通常の表記がなされる（小数点をずらして表記する）。
この範囲以外の数値は「仮数部」+「指数部」の形式で表記される。
正規化
仮数が定められた範囲内に入るように、指数部と仮数部を調整すること。
有効桁数（有効数字）
与えられた精度を保つために必要な数字の桁数。
浮動小数点は、仮数部が数値を正確に表している。
仮数部で表現できる桁数が、有効けた数である
このような事が起こるのは、浮動小数点数が常に誤差を持つものだからです。
浮動小数点数は内部で数値を２の負のべき乗の和で表現しようとします。
例えば0.875は、1/2 + 1/4 + 1/8 という形です。
残念ながら、0.1は、有限個の和では表現できません。
そのためにどうしても誤差を持つようになるわけです。
32bitの浮動小数点では、符号に1bit、数値に23bit、小数点の位置に8bit使っています。
表現できる数値は、“8.4×10(-37) ≦ |x| ≦ 3.4×1038”と“0”になります。
この表現では有効桁数が限られているため誤差が出るのですが、10進数に換算すると、およそ6桁程度の精度が得られます。
これは倍精度浮動小数点型(Double)でも同じように誤差が出るんで、ただ有効桁数が大きいだけなんだそうです。
絶対誤差
近似値から真値を代数的に引いて得られる誤差。
相対誤差
近似値から真値との比で問題にしたときの誤差。
サンプルコード
code:cpp
void put_float(char *string, float z);
int main(void)
{
float x, sum;
int i;
sum = 0.0;
x = 1.0/N;
for (i = 0; i < N; i++) {
sum += x;
}
put_float("sum = ", sum);
if (sum == 1.0) {
printf("合計は１になりました\n");
}
else {
printf("合計は１になりませんでした\n");
}
return 0;
}
void put_float(char *string, float z)
{
printf("%s%.16g\n", string, z);
}
固定小数点数 (fixed point number)
コンピュータが数値を扱うときの表現手法の一つ。
小数点が特定の位置に固定されている数値の表現手法。
表現できる数値の範囲は浮動小数点数と比較すると狭いが、計算速度は速い。 小数点を一番左に固定した固定小数点数が整数である。
整数は最も計算速度が速い。
補数（complement）
整数(固定小数点数)のコンピュータ内部での表現の仕方には、負の数をどのように表わすかによって、1の補数表現、2の補数表現、絶対値表現などがある。
基数から 1 を引いた値（例えば、10進数なら、(10-1=9）から、各桁について引き算を行い、その値に1を加えた数をいう。
たとえば、10進数の34についてその補数を求めると、(99-34) + 1 = 66 になる。 この 66 を34の「10の補数」あるいは、「10に対する補数」という。
うえで求めた補数を用いて、次の減算を考える。
50-34 = (50+66) - 100 = 116 - 100 = 16 10進数の2桁のみに着目すれば、50 と 34 の減算が 50 と 66（34の10の補数） の加算に置き換えられている。
このように、減算という演算は、補数を考えることにより、加算で行うことができる。 1 の補数表現（1's complement）
2進数の各桁のビットを反転した数を「1の補数」という。
例えば、(0101)2の1の補数は、各桁のビットを反転させて(1010)2になる。
2 の補数表現（2's complement）
1の補数に 1 を加えたのが、「2の補数」である。
例えば、(0101)2の1の補数は、各桁のビットを反転させて(1010)2になる。 これに 1 を加えて(1011)2としたのが2の補数である。
2の補数 = 1の補数 + 1
オ－バ－フロ－(overflow)とアンダ－フロ－(underflow)
コンピュータ内部での数値の表現法のゆえに、大き過ぎる数値や小さ過ぎる数はコンピュータ内では表現出来ない。
絶対値が大きくなりすぎて表現しきれなくなったときオ－バ－フロ－が起き、逆に、絶対値が小さくなりすぎて表現しきれなくなったときアンダ－フロ－が起こる。
対処例
1. スケーリング scaling
（そのうち）
2. 変数変換
（そのうち）
3. sin(x)において、大きいxは周期性を利用して|x|<π/2へ落とす。
（そのうち）
4. (n,k)=n!/((n-k)!k!)はn=15,k=5では小さな値だが15!は大き過ぎる
→ 計算途中に15!のような大きな値が出現しないように、(n,0)=1, (n,k)=(n-1,k)+(n-1,k-1) を利用した計算をする。
丸め誤差 (round error)
無限のものを有限のところで打ち切る(丸める)ことにより生じる誤差のこと。
（例） 0.1 = 0.0001100110011... 左辺は10進数、右辺は2進表現(無限小数)
これの内部表現は
0^1000000^0001100110011...001^10011...
なので32ビット目で丸める必要ある。
これにより、真の値と内部表現された値との間に誤差が生じる。
丸め誤差対策としては、倍精度型など、誤差が許容できるほど小さくなるデータ型を用いる。
桁落ち(Cancellation Error)
浮動小数点演算で、計算結果が0に極端に近くなる加減算を行ったときに、有効数字の桁数が極端に少なくなる現象。
例えば、「1.23456789x102-1.23456780x102」のような計算を行うと、計算結果は「9x10-6」となり、有効数字の桁数は9桁から一気に1桁に減少してしまう。
浮動小数点形式の値は内部的には常に有効数字の桁数を一定として扱っているため、桁落ちが発生すると、不足した桁数が自動的に0で埋められてしまい、真の値との間に誤差が発生する。
そして、桁落ちした数値に大きな数を掛けるなどの計算を行うと、発生した誤差が上の桁に上がってくることによって、計算結果を無意味にするほどの大きな誤差を含んだ値が返されることになる。
桁落ち自体による問題はコンピュータとは無関係に発生するが、コンピュータ上での桁落ちは、計算途中の値が分からない・結果の桁数が常に一定なので気づきにくいという特徴がある。
桁落ち対策としては、ほぼ等しい値の引き算がおきないように、計算式を変形する。
情報落ち(Loss of trailing digit)
2つの浮動小数点の加減算を行うときは、小さいほうの指数部を大きいほうの指数部にあわせて、仮数部の桁をずらしてから計算が実行される。
したがって、2数の多きさが極端に違うと、加減算の際に小さい数の下位の何桁かが失われて、情報が正しく活かされないことがある。
これを情報落ちという。
情報落ち誤差の回避法は「絶対値の小さい順に加えていく」。
打ち切り誤差(truncation error)
n→∞のとき収束するような公式にしたがって反復計算する際、計算を途中で打ち切る（nを有限の所で中止する）ことにより生じる誤差のこと。
多く計算すればよいというものではない。
多く計算すればするほど、丸め誤差が大きくなる。
打ち切り誤差対策としては、誤差が許容できる値以下になってから打ち切る。
入力誤差
コンピュータの精度と、コンピュータに入力する以前のデータとの精度が異なる場合、入力の段階で既に丸め誤差が発生している。
これを入力誤差という。
また、測定機器等による、物理的な誤差も、こう呼ぶ。
誤差の伝播
丸め、打ち切り、桁落ち、入力誤差を繰り返すことを言う。
教訓
実数を==で比較しないこと。
整数を利用する。
float は使うな，double を使え。
いい加減に公式を使うな，よいアルゴリズムを使え。