動機
応用情報の参考書に曖昧に書いてあったので調べたところ詰まったため記録します。
結論
結論から言うと、
- 情報落ち：状況に関わらず、大きな数と小さな数との加減算による誤差
- 積み残し：リストの総和等の演算をする際、計算する順番によっては情報落ちが起こり、それが累積した結果生じた誤差
とまとめることができます。
情報落ちの具体例
$a \ll L$として、またその間の数$m$を$a<m<L$となると考えて、$a,L$のどちらとも通常通り演算できるとします。
本当は「そのような$m$がどういう場合にあり得るのか、意味を持つか」なども考えないと以下は無駄な議論になりそうですが、イメージの話ということでご理解ください。
例として以下のように設定します。(小数点以下6桁が有効です)
$\begin{align}
a &= 7.000000\times10^{5} \\
m &= 2.997925\times10^{8} \\
L &= 1.000000\times10^{12} \\
\end{align}$
ここで次のような計算をします。
$$\begin{align}
(a + m) + L
&= (7.000000\times10^{5} + 2.997925\times10^{8}) + 1.000000\times10^{12}\\
&= (0.007000\times10^{5 + \color{red}{3}} + 2.997925\times10^{8}) + 1.000000\times10^{12}\\
&= (3.004925\times10^{8}) + 1.000000\times10^{12}\\
&= 0.000300\times10^{8 + \color{red}{4}} + 1.000000\times10^{12}\\
&= 1.000300\times10^{12}
\end{align}$$
続いて次を計算をしてみます。
$$\begin{align}
(a + L) + m
&= (7.000000\times10^{5} + 1.000000\times10^{12}) + 2.997925\times10^{8}\\
&= (\color{red}{0.000000\times10^{5 + 7}} + 1.000000\times10^{12}) + 2.997925\times10^{8}\\
&= 1.000000\times10^{12} + 2.997925\times10^{8}\\
&= 1.000000\times10^{12} + 0.000299\times10^{8 + \color{red}{4}}\\
&= 1.000299\times10^{12}
\end{align}$$
2個目の計算で、指数をそろえることで仮数部が0となってしまいました。このような状況を情報落ちといいます。
積み残しの具体例
積み残しの例として、数列$a_n = 3^{n}$を$n=1$から$n=20$くらいまで足してみましょう。
3の累乗は次のようになります。
$$\begin{align}
3^{1} &=3\\
3^{2} &=9\\
3^{3} &=27\\
3^{4} &=81\\
3^{5} &=243\\
3^{6} &=729\\
3^{7} &=2187\\
3^{8} &=6561\\
3^{9} &=19683\\
3^{10} &=59049\\
3^{11} &=177147\\
3^{12} &=531441\\
3^{13} &=1594323\\
3^{14} &=4782969\\
3^{15} &=14348907\\
3^{16} &=43046721\\
3^{17} &=129140163\\
3^{18} &=387420489\\
3^{19} &=1162261467\\
3^{20} &=3486784401\\
\end{align}$$
上の結果を表示するのに以下のプログラムをPythonで走らせました。
for n in range(1, 21):
print("3^{" + str(n) + "} &=" + str(3**n) + "\\\\\\\\")
我ながら圧倒的パワープレイ。
得られた数列の和を2通りの順番で足してみます。
指数部が煩雑なので$1.0\times10^n$を$1.0\textrm{e}1$と書きます.
小さい順で足した場合
若い順(つまり今回の例では小さい順)に足してみましょう。
こちらの場合は
$$\begin{align}
3.000000\textrm{e}0 + 9.000000\textrm{e}0 &= 1.200000\textrm{e}1 \\
1.200000\textrm{e}1 + 2.700000\textrm{e}1 &= 3.900000\textrm{e}1 \\
\cdots \\
1.743392\textrm{e}9 + 3.486784\textrm{e}9 &= 5.230176\textrm{e}9 \\
\end{align}$$
となりました。
大きい順に足した場合
次に逆の順で足してみましょう。
最初に一番大きな$3486784401=3.486784\textrm{e}9$を足すため以下のようになります。
$$\begin{align}
3.486784\textrm{e}9 + 1.162261\textrm{e}9 &= 4.649045\textrm{e}1 \\
4.649045\textrm{e}9 + 0.387420\textrm{e}9 &= 5.036465\textrm{e}9 \\
\cdots \\
5.230166\textrm{e}9 + 0.000000\textrm{e}9 &= 5.230166\textrm{e}9 \\
\end{align}$$
足した順による結果の比較
真の値は$5230176600$で$5.230176\textrm e 9$となるのが正しい計算結果です。
- 小さい順の値との誤差: $5.230176 - 5.230176 = 0.000000$
- 大きい順の値との誤差: $5.230176 - 5.230166 = 0.000010$
順番が違うことによる誤差が見られますね。この例だと大した差に見えないかもしれませんが。
このような、計算をする順番によって絶対値の小さな値が足されなくなる(引かれなくなる)ことで生じる誤差を積み残しといいます。
まとめ
今回は似ている概念の違いを確認しました。
改めて書けば
情報落ち：絶対値の大きな数と小さな数との加減算による誤差
積み残し：計算する順番に起因する情報落ちが累積した結果として生じた誤差
というわけです。
以上が個人的な(イメージとしての)両者の違いです。見当はずれな点などございましたらご指摘いただけると幸いです。ここまでお読みいただきありがとうございました。
参考
こちらの記事を参考にしました。
浮動小数点演算の罠(@tomabou),2019年09月28日