情報落ち

この章の目標

絶対値の大きく異なる数の加減算で小さい方の情報が失われる情報落ちの発生メカニズムを理解する。桁落ちとの違い、Kahan 補償加算やペアワイズ加算などの対策を把握する。

前提知識

目次

1. 定義

情報落ち（Loss of Trailing Digits、または Absorption）とは、絶対値の大きく異なる2つの浮動小数点数を加減算した際に、小さい方の数の下位桁（有効数字の一部または全部）が失われる現象である。

情報落ちの本質

浮動小数点加算では、指数を揃えるために小さい方のオペランドの仮数部を右にシフトする。シフトにより仮数部の表現範囲外に押し出された桁は切り捨てられ、情報が失われる。

2. 発生メカニズム

10進4桁の浮動小数点数で $1.000 \times 10^4 + 5.678 \times 10^0$ を計算する。

指数を揃える: $5.678 \times 10^0 = 0.000\,5678 \times 10^4$

4桁の仮数部に収まる範囲: $0.000\,5 \times 10^4$（下位3桁 $678$ が失われる）

加算: $1.000 \times 10^4 + 0.000 \times 10^4 = 1.000 \times 10^4$

小さい方の数 $5.678$ が完全に吸収されてしまい、加算の効果がまったく反映されない。

← 仮数部 4 桁 → 仮数部の範囲外 大きい数: 1 0 0 0 × 10⁴ 小さい数: 0 0 0 0 5 6 7 8 × 10⁴ 失われる! 結果: 1 0 0 0 × 10⁴ 小さい数が吸収された 指数を揃える際に小さい数の有効桁が仮数部の範囲外に押し出され、情報が消失する
図1. 情報落ちのメカニズム。指数を揃えるために小さい数の仮数部をシフトした結果、有効桁が仮数部の範囲外に押し出される。

3. 総和計算における情報落ち

多数の数の総和を計算する際、累積和が大きくなるにつれて各項の加算で情報落ちが深刻化する。

例えば $\displaystyle\sum_{k=1}^{n} 1/k$（調和級数の部分和）を $k = 1$ から順に計算すると、$n$ が大きくなると累積和に対して $1/k$ が極端に小さくなり、情報落ちが発生する。$k = n$ から逆順に計算する方が精度が良い。

$n = 10^7$ の場合、順方向の加算と逆方向の加算で結果が異なることを確認できる。

4. 対策

ソート加算

絶対値の小さい数から順に加算することで、累積和と各項のスケール差を最小化する。実装が容易であるが、最善の対策ではない。

Kahan の補償加算

失われた下位桁を変数 $c$ に蓄積し、次の加算で補償する。

function kahanSum(values):
    sum = 0.0
    c   = 0.0
    for v in values:
        y = v - c         // 前回の補償を適用
        t = sum + y       // sum は大きいので y の下位桁が失われる
        c = (t - sum) - y // 失われた分を c に記録
        sum = t
    return sum

補償変数 $c$ には、$\text{sum} + y$ を計算したときに $y$ の下位桁が累積和に吸収されて失われた分が記録される。次のループの先頭で $y = v - c$ とすることで、前回失われた下位桁を取り戻して加算する仕組みである。Kahan 加算の誤差は $O(\varepsilon_{\text{mach}})$ であり、項数 $n$ に依存しない。誤差上界 $|S - s_n| \le 2u|S| + O(nu^2)$ の証明、Fast2Sum との等価性、入力大小に頑健な Neumaier 改良については中級「補償付き加算」を参照。

ペアワイズ加算

配列を半分に分割し、再帰的に各半分の和を計算して合計する。誤差は $O(\log n \cdot \varepsilon_{\text{mach}})$ であり、キャッシュ効率もよい。NumPy の sum はペアワイズ加算を使用している。

正負分離加算

正負が混在するデータでは、上記いずれの方法でも累積和が 0 付近を跨いで桁落ちが発生する。正の項と負の項を分け、それぞれを絶対値の小さい順に総和し、最後に一度だけ引き算するとよい。

  1. 正の項を絶対値の昇順で累算 → $P$
  2. 負の項を絶対値の昇順で累算 → $N$
  3. $P + N$ を計算 (引き算は 1 回のみ)

各部分和の累算は符号が一定なので、ほぼ等しい値の引き算による桁落ちは原理的に発生せず、桁落ちは最終減算 1 回に集中する。ただし情報落ち (累積和と各項のスケール差による下位桁の喪失) は各部分和の中で依然発生し得る。Kahan 加算は情報落ちには効くが累積和が 0 を跨ぐ際の桁落ちには無力で、ペアワイズ加算も同様である。正負分離はこの弱点を補い、両者と組み合わせると相補的に効く。

  • 正負分離 + Kahan: $P, N$ をそれぞれ Kahan 加算で求めると、各部分和の情報落ちが補償されて誤差は $O(\varepsilon_{\text{mach}})$ となり、最終減算 1 回分の桁落ちのみが残る。
  • 正負分離 + ペアワイズ加算: $P, N$ を再帰的に半分ずつ加算する。各部分和の誤差は $O(\log n \cdot \varepsilon_{\text{mach}})$ で、Kahan 版より高速 (補償計算がない分)。

5. 桁落ちとの比較

性質情報落ち桁落ち
原因絶対値の大きく異なる数の加減算ほぼ等しい値の減算
失われるもの小さい方の下位桁結果の上位有効数字
発生する演算加算・減算どちらでも減算のみ
影響小さい値の寄与が消失相対誤差の爆発的増大
主な対策演算順序の工夫、補償加算数式変形、テイラー展開

6. 計算例

例1: 大きな数への小さな数の加算

倍精度（約15桁の有効数字）で以下を計算する。

a = 1.0e16
b = 1.0
print(a + b)      // 出力: 10000000000000000.0（b が吸収された）
print(a + b == a) // 出力: true

$10^{16}$ は16桁の数であり、$1$ を加えるには17桁目が必要であるが、仮数部は約15桁しか保持できない。

例2: 調和級数の部分和

$H_n = \displaystyle\sum_{k=1}^{n} 1/k$ を $n = 10^7$ で計算する場合：

  • 順方向（$k = 1, 2, \ldots, n$）: 累積和が大きくなるにつれ $1/k$ の情報落ちが増大
  • 逆方向（$k = n, n-1, \ldots, 1$）: 小さい値同士がまず加算されるため精度が向上
  • Kahan 加算: 方向に依存せず高精度

7. よくある質問

Q1. 情報落ちとは何ですか？

絶対値の大きく異なる2つの浮動小数点数を加減算した際に、小さい方の数の下位桁が失われる現象である。大きい数に小さい数が「吸収」されてしまう。

Q2. 情報落ちと桁落ちの違いは何ですか？

情報落ちは絶対値の大きく異なる数の加減算で小さい方の情報が失われる現象であり、桁落ちはほぼ等しい値の減算で有効数字が失われる現象である。情報落ちは加算でも発生する。

Q3. 情報落ちの対策は何ですか？

小さい値から順に加算する（ソート加算）、Kahan の補償加算で失われた下位桁を補償する、ペアワイズ加算で再帰的に半分ずつ加算する、数式を変形してスケール差の大きい加減算を避ける、などの方法がある。

8. 参考資料

  • Wikipedia「情報落ち」（日本語版）
  • Wikipedia「Catastrophic cancellation」（英語版で「Loss of significance」はこの記事に統合されている）
  • Wikipedia「Kahan summation algorithm」（英語版）
  • D. Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic," ACM Computing Surveys, vol. 23, no. 1, pp. 5--48, 1991.
  • N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002.