補償付き加算の概要
補償付き加算（compensated summation）とは、浮動小数点数の加算で生じる丸め誤差を減らすことを目的として、通常の和に加えて補正量（補償項）を同時に更新しながら結果を求める手法の総称である。単純な逐次和では、桁落ちや丸めにより誤差が累積しやすいが、補償付き加算はその一部を別途保持・反映することで、実効的な精度を改善する。
代表的には、各加算ステップで「丸めによって失われた成分」を補償項として保持し、次の加算に繰り込む設計となっている。これにより、同じ浮動小数点形式のまま、より良い近似（特に和の精度）を狙う。
浮動小数点加算の誤差要因
浮動小数点加算における誤差は、主として丸めと表現限界に起因する。具体的には、加算結果が仮数の有効桁数を超えると、余分な成分が丸められて情報が失われる。このとき、特に加える値の大きさが大きく異なる場合には、有効桁の一致が不十分になり、より小さい成分が目立たなくなる（桁落ち）。
また、逐次的な計算では誤差がステップごとに蓄積し、最終結果の誤差構造が単純な一回の丸めとは異なるものになる。加算順序や入力の性質（符号の混在、スケールの偏り、同程度の大きさが多数回出現するか等）により、誤差の増え方は変化する。
補償付き加算の目的と効果
補償付き加算の狙いは、単純な逐次和で失われる「丸めによる欠損成分」を再利用し、最終的な和の誤差を抑えることにある。計算は浮動小数点演算のみで行われるのが一般的だが、補償項を介して有効情報を保持する点が特徴である。
効果としては、特に桁落ちが起こりやすい状況、あるいは多数の項を足し合わせる場合に、通常加算よりも精度が改善されることが多い。改善の度合いは入力データの分布と加算順序に依存するため、常に同程度の改善が保証されるわけではない。
精度向上の基本原理
補償付き加算では、各ステップの加算で生じた丸め差を補償項として分離する発想が中心にある。通常の和演算は「正確な和」ではなく「丸められた近似値」を返すため、差分（近似に含まれなかった成分）が生まれる。補償付き加算は、この差分を次の計算に取り込むように設計されている。
典型的には、まず現在の累積値に新しい項を加えて近似の和を得る。次に、その近似が本来含むべき成分からどれほど離れたかを、浮動小数点演算だけで推定し、その推定値を補償項として更新する。そして最終的な累積に、補償項を介して修正を反映する。この流れにより、丸めで失われた情報を完全に取り戻すことはできないとしても、次のステップで誤差が増えにくい形に再配置できる。
また、補償項の取り扱いは「補償しすぎ」にならないように、浮動小数点で整合した形で更新される必要がある。設計が不適切だと、補正量が自己増幅して逆効果になることがあるため、演算の順序と式の組み立てが重要になる。
計算コストとのトレードオフ
補償付き加算は通常加算より多くの演算を必要とする。具体的には、補償項を更新するための追加の差分計算や、丸め差を推定するための演算が入るため、1回あたりの計算量が増える。
このため、精度が必要な場面では有効だが、精度要求が低い用途や計算資源が非常に制約されている場合には、導入の妥当性が検討対象になる。実務では、許容誤差、データ規模、計算基盤の性能特性（分岐のコスト、ベクトル化の可否、利用可能な演算命令）を踏まえて、補償付き加算を使うか、別の改善（加算順序の工夫、階層和、より高精度の型）で対応するかが判断される。
基本アルゴリズム
補償付き加算の基本アルゴリズムは、補償項を更新しながら逐次的に和を構成する枠組みに基づく。ここでは代表としてケイハン加算を取り上げ、変数の役割、更新の流れを整理する。その後、近縁の手法の呼称を整理し、実装時の注意点を述べる。
設計の要点は、補償項が「丸め差の推定値」として振る舞うように、差分の計算と合成のタイミングを整えることにある。浮動小数点環境の丸めモードや例外挙動が想定と異なると結果が変わりうるため、移植性にも配慮が必要になる。
ケイハン加算
ケイハン加算（Kahan summation）は、補償付き加算の代表例として広く知られる。単純な逐次和に補償項を追加し、各ステップで丸め誤差の影響を抑える構造になっている。理論的にも実務的にも、特に桁落ちが問題になる和の計算で性能を発揮する。
ケイハン加算の特徴は、補償項を単なる記録ではなく、次の累積値に反映するための補正として用いる点にある。これにより、誤差が蓄積する過程を制御しようとする。
変数の役割（和と補償）
ケイハン加算では、一般に少なくとも2種類の変数が用いられる。通常の累積値（和）と、誤差を補正するための補償（補償項）である。
和の変数は、現在までに処理した項の近似和を保持する。一方、補償項の変数は、直前の加算で丸めにより失われた成分の推定値を保持し、次の加算で利用される。さらに、更新の途中で一時的な差や補正候補を作る場合があるが、それらは補償の見積りや適用のための補助的役割を担う。
ケイハン加算の式は、浮動小数点の丸め結果が前提となるため、変数の更新順序は数値的性質に影響する。実装では「どの値をどのタイミングで計算・反映するか」を崩さないことが重要になる。
典型的な更新手順
典型的には、次の流れで各項を処理する。まず補償項を反映した補正済みの増分を作り、次にそれを累積値に加える。加えた結果から、実際に累積値へ反映された分と、意図した分との差を推定し、その差を補償項として更新する。
もう少し具体化すると、現在の累積値に新しい項を足す際、補償項を引いた（または符号に応じて組み込んだ）補正済みの増分を用いる。次に累積に対する加算を行い、その加算結果がどれだけ「意図した増分」を取り込んだかを計算する。取り込めなかった成分が丸めによって失われた成分として扱われ、補償項の更新に使われる。
この手順により、失われた成分が補償項として保持され、次回以降の増分に再度影響しうる。結果として、逐次和で誤差が急増する場面でも、誤差の増え方が緩和されることが多い。
近縁手法と呼称の整理
補償付き加算には複数の変種があり、文献や実装ライブラリによって名称が揺れることがある。たとえばケイハン加算の他にも、改良型ケイハン加算、Neumaier和、ペアワイズ和（階層的加算）などが、誤差低減の目的で言及されることが多い。
近縁手法は「補償項を1つ持つか複数持つか」「丸め差の推定方法」「加算の構成（逐次か階層か）」の違いで整理できる。呼称の違いは、理論的な導出よりも実装上の差（式の形や更新の順序）に由来する場合があるため、比較する際は、同じ入力条件で同程度の性能が得られるか、数値的に同じ誤差モデルに基づくかを確認することが望ましい。
ここでは、補償項の扱いを中心に捉えることで、ケイハン加算と類似した性格の手法群を理解しやすくする。
擬似コード例と実装上の注意
擬似コードとしては、累積値 sum と補償 c を用い、各要素 x について補正済みの増分を作り、それを累積に加え、差分から補償を更新する形になる。実際の式は採用する変種により微差があるが、実装上の核は「丸め差を推定し、補償に反映する」点にある。
実装上の注意として、次の点が重要である。第一に、浮動小数点演算が高速化のために再関連付（fast-math的最適化）されると、計算の順序や丸めのタイミングが変わり、期待した補償性が損なわれる可能性がある。第二に、スカラー計算として書いた場合でも、コンパイラや言語仕様によっては、評価順序が不定になりうる。副作用のない純粋計算でも、式の変形が行われると結果が変化することがあるため、実装では許容される変形を把握する必要がある。
さらに、並列化する場合には、処理順序が変わるため誤差の性質も変化する。補償付き加算を並列要素ごとに適用し、その結果を最終的に再度合成する方針が取られることが多いが、合成段階でも同様の補償戦略を適用するかどうかが精度に影響する。入力の符号が混在するか、値のスケール差が大きいかといった性質も評価対象となる。
数値精度の評価
補償付き加算の有効性は、誤差解析と比較指標によって評価される。ここでは、誤差解析の考え方を示したうえで、通常の逐次加算との比較に使われる尺度、さらに収束性・安定性の観点を整理する。評価では、理論的な解析だけでなく、実データでの検証も重要である。
誤差解析の考え方
誤差解析では、計算結果が真値（数学的な和）からどの程度乖離するか、そしてその乖離が入力の特徴にどのように依存するかを検討する。浮動小数点演算では丸め誤差が各演算に介在するため、逐次和の誤差は演算回数とともに変化しうる。
補償付き加算では、丸め差の一部を補正として再利用するため、誤差の蓄積の仕方が通常の和とは異なる。したがって解析では、「補償項が誤差に対してどのような役割を果たすか」を念頭に置く必要がある。厳密な上界評価は手法ごとに複雑になりやすい一方、実務的には、通常加算に比べて誤差が抑えられる傾向を定性的・定量的に把握することが主眼となる。
また、評価対象をどのように定義するかも重要である。絶対誤差の小ささを重視するのか、相対誤差の安定性を重視するのかで、結論が変わりうる。さらに、丸めモードがデフォルトから変更されていると誤差挙動が変わる可能性があるため、実験条件の明示が求められる。
通常加算との比較指標
通常の逐次加算と比較する際には、誤差の尺度を揃えることが必要である。代表的には絶対誤差と相対誤差が用いられ、加えて数値計算としての性質（安定性）を見る観点も併用されることが多い。
絶対誤差・相対誤差
絶対誤差は、計算された和と真の和（高精度参照値）との差の大きさである。桁落ちやスケールの偏りがある場合、絶対誤差は入力の大きさに強く依存し、見え方が偏ることがある。
相対誤差は、真値に対する誤差の比であり、真値が大きい場合と小さい場合で評価のバランスを取れる。ただし、真値がゼロ付近にあると相対誤差が不安定になり、比較が難しくなる。このため、真値が符号反転して小さくなるようなデータ（差分に相当する状況）では、別の指標や領域別の評価が必要になる。
補償付き加算の比較では、これらの尺度に加えて、誤差の分布（最大値、平均値、分位点）を見て、典型ケースと悪条件の両方で改善が得られるかを確認することが有用である。
収束性と安定性の観点
和の計算は「繰り返し回数を増やしたときに誤差がどのように増減するか」という意味で、収束性や安定性の観点が関与する。補償付き加算は逐次的に処理しながら補正を加えるため、誤差の増え方が抑制される傾向が見込まれる。
安定性は、入力の微小な摂動に対して出力が過度に変化しないかという観点である。補償項を含む手法は、特定の誤差成分を再配置するため、単純な逐次和より安定なふるまいを示す場合があるが、入力の特徴によっては限定的な改善に留まることもありうる。したがって、特定の条件（値の符号、分布、順序）を固定した上で、通常加算との比較を行うことが望ましい。
実験では、同一の真の和に近い参照値を用い、要素数を変えたり、順序をシャッフルしたりして、誤差のばらつきを観察することで、実際の安定性を推定できる。
応用分野と実装パターン
補償付き加算は、誤差が意味を持つ場面で応用される。大規模和、科学技術計算、並列・ベクトル化、そして品質保証という観点で実装パターンを整理する。どの場面でも、精度と性能のバランス、再現性の確保、検証の設計が鍵となる。
大規模和の計算（積算・総和）
大量の項を足す積算や総和では、通常の逐次加算により誤差が累積しやすい。補償付き加算は、これらの処理で誤差の増加を抑える目的で利用されることがある。
ただし大規模データでは計算量とメモリ帯域がボトルネックになりやすい。補償付き加算は追加演算を伴うため、単純に全ての箇所に適用すると性能劣化が起こりうる。このため、入力の性質（値のスケール差、符号の混在度、要求精度）に基づいて適用範囲を決める運用が一般的になる。
また、区間ごとに和を計算し、最後に合成する階層方式（チャンク化）と組み合わせると、精度と性能の両立が図りやすい。補償付きの処理をどのレベルで行うかが設計のポイントになる。
科学技術計算における利用
科学技術計算では、物理量の総和や積分の近似など、和が後続の計算に強く影響することがある。たとえば観測データの集計、エネルギーや期待値の算出、コスト関数の評価などでは、和の誤差が最終的な判断に波及する可能性がある。
この種の用途では、補償付き加算は「同じ入力でより正確な中間量を得る」手段として位置付けられる。特に、桁落ちが起きやすい成分同士の相殺が含まれる場合に有効となることがある。
一方で、科学計算の多くは他にも誤差源を持つ。丸めだけでなく、境界条件、離散化誤差、モデル化誤差などが存在するため、補償付き加算の導入による改善が全体精度にどの程度寄与するかを見積もる必要がある。したがって、精度向上の対象が本当に和の丸め誤差支配かどうかの評価が重要になる。
並列計算やベクトル化での扱い
並列計算では、計算順序が実行環境により変わることが多い。そのため、逐次の補償付き加算と同じ誤差特性を維持するのは難しくなる場合がある。典型的な対策として、各スレッドまたは各ワークユニットで部分和を計算し、その部分和の合成にも同様の補償戦略を適用する設計が用いられる。
ベクトル化では、補償項を持つ分岐の多い更新が効率を落とすことがある。そこで、可能な場合には、SIMD（単一命令・複数データ）に適した形へ式を整理し、局所的に補償を適用するパターンが検討される。実装の自由度は言語とコンパイラに依存するため、最適化レベルでの挙動差を実測しながら調整するのが現実的である。
並列環境での再現性は特に注意が必要である。補償付き加算は逐次順序への依存が残るため、スレッド数やスケジューリングが変わると結果が微妙に変動する可能性がある。厳密な再現性が要件なら、合成順序やデータ分割方法を固定するなどの工夫が求められる。
実装品質（再現性・性能・検証）
実装品質の観点では、再現性、性能、検証の3つをまとめて扱うのが実務的である。再現性では、同一の入力から同一の出力が得られることを狙うが、並列化や最適化、丸めモードの違いがあると差が生じる。したがって、丸め設定、コンパイラ最適化指針、実行環境の差分を管理し、必要に応じて条件を固定することが重要になる。
性能では、補償のための追加演算が支配的かどうかを評価する。特にメモリアクセスが支配的な場合は、演算増加による悪影響が相対的に小さいこともある。一方、演算が支配的な状況では、速度低下を抑えるための実装（チャンク化、ループ構造の工夫、ベクトル化との両立）が求められる。
検証では、参照値の作り方が要点になる。高精度計算（多倍長、あるいは適切な精度のライブラリ）を用いて真値の近似を準備し、絶対誤差・相対誤差や入力順序の揺らぎに対する頑健性を確認する。テストケースは、ランダムデータだけでなく、桁落ちを誘発しやすい条件や符号が混在する条件を含めると、補償付き加算の価値を適切に見積もれる。