Quantum Sea

タグ: Kahan補償和

  • Kahan補償和、丸めで消えた小さな加算を次へ持ち越す仕組み

    Kahan補償和、丸めで消えた小さな加算を次へ持ち越す仕組み

    大きな合計に小さな値を足し続けているのに、計算結果が増えない。浮動小数点数での集計では、こうしたことが起こります。小さな値が入力されていないのではなく、加算のたびに丸められ、合計へ残らないためです。

    Kahan（カハン）補償和は、合計とは別に小さな補正値を持ち、次の加算へ引き継ぐ方法です。どんな計算も正確にするわけではありませんが、消えた増分を毎回捨ててしまう問題を抑えられます。数値を集計するとき、データの件数だけでなく、大きさと符号にも目を向ける理由が見えてきます。

    簡単にまとめると？

    • 浮動小数点数は表せる値が飛び飛びなので、大きな合計へ小さな値を足しても、丸めで元の値に戻ることがあります。
    • Kahan補償和は、加算で生じたずれを補正値として持ち、次の入力へ加えます。合計と補正値の2つを使うのが要点です。
    • 正負の大きな値が相殺する場合など、補償和でも誤る例があります。入力順と実際の数値範囲で、精度の高い参照計算と比較する必要があります。

    10¹⁶に1を足しても増えないのはなぜか

    ここでは、有効桁が2進数で53ビットのbinary64と、最も近い値へ丸め、ちょうど中間なら末尾のビットが偶数になる側を選ぶ「最近接偶数丸め」を考えます。多くの環境で使われるPythonのfloatに対応する条件です。[1]

    10¹⁶、つまり10,000,000,000,000,000の近くでは、binary64で隣り合う値の間隔は2です。10¹⁶と10¹⁶＋2は表せますが、その間の10¹⁶＋1は表せません。10¹⁶へ1を足した結果は、この丸め方では10¹⁶へ戻ります。

    次にもう1を足しても、出発点はまた10¹⁶です。同じことを1万回繰り返しても、途中の合計を1つのfloatだけに保存する順次加算では、増分が一度も残りません。大きな値が先に入った集計ほど、後から届く小さな寄与を取りこぼす可能性があるわけです。

    消えた分を、次の入力に持ち越す

    Kahan補償和では、合計sに加えて補正値eを保存します。次の入力xへ前回の補正を加え、その結果を合計へ足した後で、新しいずれを求めます。Highamの論文で示された形を、Pythonで書くと次のようになります。[2]

    def kahan_sum(values):
    s = 0.0
    e = 0.0
    for x in values:
        old = s
        y = x + e
        s = old + y
        e = (old - s) + y
    return s

    10¹⁶を合計に持った状態で最初の1を加えると、sは増えません。しかし、(old - s) + yは0 + 1となり、補正値eに1が残ります。

    次の1が来ると、前回の1を合わせてy = 2になります。今度は10¹⁶＋2を表せるので、合計が2だけ増えます。小さな寄与を別の変数へ逃がすことで、主な合計に入る大きさになるまで持ち越せたのです。

    補正値は常に正とは限りません。丸めが上側へ働いた場合には負の補正が残ります。また、(old - s) + yは、実数の代数式として整理するための式ではありません。括弧の順序で丸めを含む計算を行うことに意味があり、処理系の最適化で演算が並べ替えられるときは、この順序が保たれるかを確認する必要があります。

    1万回の加算を、実際に比べる

    10¹⁶の後に1を1万個並べ、単純な順次加算と上のKahan補償和で計算しました。参照値は、入力を正確な有理数に変換して求めた和です。今回の入力はすべて整数で、入力時の変換では誤差を生じていません。

    10の16乗に1を1万回加えたときの増分。単純な順次加算は0、Kahan補償和と整数での厳密な和はともに10000。binary64・最近接偶数丸めでの独自計算。
    10¹⁶からどれだけ増えたかを比較。Python 3.12.14のbinary64環境でQSが計算。単純な順次加算は、ループ内で1つずつ加える実装です。

    単純な順次加算の結果は10,000,000,000,000,000、Kahan補償和は10,000,000,000,010,000でした。後者はこの例の厳密な和と一致します。

    同じ入力でも、1を1万個先に足して最後に10¹⁶を加えると、今回の単純加算も厳密な和に一致しました。失われる量は、値の組合せだけでなく順序にも左右されます。なお、ここでいう単純加算は明示的な加算ループであり、Pythonの組込み関数sum()全般を指しているわけではありません。

    大きな値どうしが相殺すると、補償和でも誤る

    では、[10¹⁶, 1, −10¹⁶]という順序ではどうでしょうか。厳密な和は1ですが、同じ実装で計算すると、単純加算もKahan補償和も0になりました。

    小さな1はいったん補正値に残ります。ところが、最後の入力−10¹⁶へその1を加える段階で、また丸めが起こり、yは−10¹⁶になります。そこで正負の10¹⁶が打ち消し合い、残したかった1が消えます。補正を次の入力へ足す操作自体にも、有限の精度という限界があるのです。

    この例では、Pythonのmath.fsum()は1を返しました。公式文書では、複数の部分和を追跡して精度を高める関数として説明されています。[3] ただし、それは上のKahan補償和と同じ実装という意味ではなく、公式文書にも丸めや環境に関する条件があります。

    集計方法を選ぶときに確かめたいこと

    まず、大きな値の後に小さな値が続く入力と、正負の大きな値が打ち消し合う入力を分けて試します。今回の2例のように、片方で改善しても、もう片方では誤差が残ることがあるからです。入力順を変えた結果も比較すると、順序への敏感さが分かります。

    次に、合計がほぼ0になる場合は、相対誤差だけで判断しないことも大切です。小さな参照値で割ると相対誤差が大きくなるため、用途上許せる絶対的な差も合わせて見ます。参照値には、十分な精度を持つ計算や、入力値を正確に扱う計算を使います。

    そして、入力された時点で失われた情報は、足し方を変えても戻りません。例えば、本来10¹⁶＋1だった値を先にfloatへ丸めて10¹⁶にしてしまえば、補償和に届く前に1が消えています。Kahan補償和が扱うのは、与えられた数を足す途中の誤差です。入力の表現、足す順序、使う集計関数をそれぞれ確認することが、結果を信頼できる範囲を決めます。

    出典

    1. Python 3.15.1 documentation — Floating-Point Arithmetic: Issues and Limitations。binary64の精度と入力表現。資料の版と本文の計算環境は区別しています。
    2. Nicholas J. Higham, The Accuracy of Floating Point Summation, SIAM Journal on Scientific Computing, 14(4), 783–799, July 1993。Kahan補償和とその条件はpp.790–791。
    3. Python 3.15.1 documentation — math.fsum。部分和を用いた集計と丸め条件。