情報落ちについての質問です。
以下のプログラムで 1/n
を n
回加算しているのに、答えが 1.0
にならない理由を教えてください。
float f = 0.0;
int n = 100000;
for(int i = 0; i < n; i++) {
f += 1.0/n;
}
println("f = " + f);
厳密に説明すると難しくなるのでたとえ話を含めて
「10進数表記で正確に表現できる数」であっても「2進数表記で正確に表現できない」ものは(提示の 1/100000
はまさにこれ)2進数表記では循環小数になります。コンピュータのメモリは有限なので無限桁数を扱うことはできません。なのでどこか適当なところで打ち切る必要があります。すると真の値とは必ず誤差が生じます。これを打ち切り誤差と言います。
それは例えば 1/3
を「3進数表記」すれば正確に表現できるのに対して「10進数表記したら循環小数になる」のと同じです。 0.33333
で打ち切った数値は正確に 1/3
ではありません。打ち切った結果として真の値と異なってしまいます。
さて、これ (1/3
ないしは 0.33333
) を加えていくことを考えます。
1/3 + 1/3 + 1/3
を3進数表記したら 0.1 + 0.1 + 0.1
ですから 1
が得られて正確な結果となります(float
がそうであるようなコンピュータはありませんが)
10進数表記で 0.33333 + 0.33333 + 0.33333
だと結果は 0.99999
になりそうです。よって打ち切り誤差 だけが 累積する場合は、正の数の和の結果は真の値より必ず小さくなります。
コンピュータ内部でこの手の浮動小数点数を扱う際には打ち切り誤差とは別に「丸め誤差」が生じます。丸め誤差とは「正しく表現できない数を、正しく内部表現できる数で代用する場合に、どの数を選ぶか」で生じます。先ほどの 1/3
は 0.3333....
無限桁は表現できないので 0.33333
で打ち切ったわけです。では 2/3
を 0.66666
とするか 0.66667
とするかは案件・要望によって異なります。より誤差の小さい数値に丸めた結果は元の数値より大きい値になることがあります。
提示例は「打ち切って小さくなる」「丸めて大きくなる」の両方が生じた結果、たまたま大きい方向になったという代物です。
java でこの制御ができるかどうか知らんので c のサンプル MSVC
だと、この辺の「丸め方向」を _controlfp()
で制御できます。今どき流に _s
なブツを使ってみると
#include <stdio.h>
#include <float.h>
int main() {
unsigned int fp;
_controlfp_s(&fp, 0, 0);
_controlfp_s(&fp, _RC_CHOP, _MCW_RC);
float f = 0.0;
int n = 100000;
for (int i = 0; i < n; i++) {
f += 1.0 / n;
}
printf("f = %g\n", f);
}
上記例題で _RC_CHOP
は「0方向への丸め」(絶対値が小さい最近値へ丸める)ですが、こうすると結果は 0.997263
と小さくなります。 _RC_NEAR
は「最も近い値へ丸め」(標準設定)で、これだと結果は 1.00099
と大きくなります。既に回答・コメントにある n=104857
の場合とか _RC_UP
とか _RC_DOWN
とか、加算する数が負の時どうなるかとかをいろいろ試すと理解が深まると思います。
_RC_NEAR
相当) とされているようです(ごく一部例外あり)。
浮動小数点数は概数であり、1.0/100000
は正確には0.000001
を表しておらず誤差を含んでいます。
f += 1.0/n;
を100000回実行することで誤差も100000倍に増幅されます。そのため、f
が1.0
にはなりません。
打切り誤差
無限小数などの計算を途中で打ち切ることなどによって生じる誤差(中略)
情報落ち
浮動小数点演算において,絶対値の大きな数と絶対値の小さな数の加減算を行ったとき,絶対値の小さな数の有効けたの一部又は全部が結果に反映されない誤差
質問文中のコードで発生しているものは「情報落ち」による誤差ではなく「打ち切り誤差」です。
10進数表現である 1/100000 (0.00001)
は有限小数ですが、プログラム内では2進数で表現され、これは無限小数(0.000000000000000010100111110001011010110001000111000110110100011110001...
)になります。
このため打ち切り誤差が発生します。
参考:
質問者の「情報落ち」であってると思います。
https://www.cc.kyoto-su.ac.jp/~yamada/programming/float.html
浮動小数点には無限小数を float にすると 有効桁 2進数 23ビットで表すための 『丸め誤差』があり
打切り誤差
無限小数などの計算を途中で打ち切ることなどによって生じる誤差
桁落ち
値が近い二つの数を引き算することにより,その有効桁数が落ちる
情報落ち
絶対値が大きな値と小さな値とを加えた場合,小さい方の数値がもつ情報が失われる
等の誤差が発生します。
この 計算の問題点は 1/100000 を 加算していくときに
float 型の精度は約6桁なのでだんだん 足す数と足される数の有効桁数が違って
くるため「情報落ち」が発生する事です。
1/100000 は float で 約 0.000009999999747 (有効桁6ケタ)なので
最初の足し算では
0.000009999999747 (有効桁6ケタ)
+ 0.000009999999747 (有効桁6ケタ)
のように 有効桁数が近い間は 有効桁6ケタ同士の加算では 情報落ち がありませんが
計算が進んでくると
0.12345678 (有効桁6ケタ)
+ 0.000009999999747 (有効桁6ケタ)
のように 足す数と足される数の小数点位置がズレてくるため
足す方の数が有効桁数 1、2桁しか使われなくなります。
これが「情報落ち」で だんだん足し算の誤差が増えてきます。
プログラムを見たときに
最初の方は 有効桁6桁+有効桁6桁の足し算だったのに
ああ f が 1 に近づくにつれて
有効桁6桁 + 有効桁2桁 の足し算になってるな・・
精度悪そう・・。
最終的な有効桁は3桁程度か・・?。
最終的な計算結果を有効桁6桁にするなら途中計算は double で 有効桁15桁で
計算しないとだめだな・・。
と判断できるようと思います。
プログラムで 1/n を n 回加算しているのに、答えが 1.0 にならない理由を教えてください。
浮動小数点の計算には 『丸め誤差』による誤差があり
今回の計算方法では 下記のような 情報落ちが累積してより大きな誤差が発生しています。
有効精度 6桁の足し算を10回
有効精度 5桁の足し算を90回
有効精度 4桁の足し算を900回
有効精度 3桁の足し算を9000回
有効精度 2桁の足し算を90000回
しているため 合計の計算結果の 最終的な有効桁数は 2桁~3桁程度だと思われます。
計算結果の 1.000990152
は 1.0
の 有効桁 2~3桁の範囲内なので
この計算方法としての 想定内の結果です。
1.0/100000
をfloatで表現すると、9.999999747e-06
(10進数)となり、
正確な値より小さくなります。
しかし、1.0/100000
を100000回足した結果は1.000990152e+00
となり、
正確な値より大きくなります。
そのため、1.0/100000
をfloatで表現した際の丸め誤差だけでは説明ができません。
理由の説明のため、大きい数値との足し算を実際にやってみます。
1.0/100000
をfloatで表現すると、1.01001111100010110101100 x 2^-17
(2進数)となります。
これと0.5
(floatで1.00000000000000000000000 x 2^-1
)と足し合わせてみましょう。
まずは両者の桁を合わせて
0.000000000000000101001111100010110101100 x 2^-1
1.00000000000000000000000 x 2^-1
足し合わせて
1.000000000000000101001111100010110101100 x 2^-1
floatの有効桁(小数点以下23桁)の下で偶数への丸めを実施します(この場合四捨五入と同じ結果)。
1.00000000000000010101000 x 2^-1
この場合、切り上げが発生することがわかると思います。
さて、0.5以上1.0未満の数字であれば、floatで1.xxxxxxxxxxxxxxxxxxxxxxx x 2^-1
という形になります。
小数点以下23桁未満の数値が存在しないことから、1.0/100000
と足し合わせると
小数点以下23桁未満の数値はすべて1.0/100000
と同じ値になります。
つまり、0.5との足し算の場合と同様、足し算の結果は常に切り上げになることが分かります。
(厳密には、足した結果が1.0以上になる場合は切り上げになるか不明ですが、ループでの加算中1回しか発生しないので影響は軽微です)
ループでの1.0/100000
との足し算のうち、0.5以上1.0未満(全体の半分)の範囲がほぼすべて切り上げになることから、
結果が大きい方に偏るのは理解していただけるのではないでしょうか。