総和の計算は、なぜどのように難しいのか

プログラミング入門で、forループを使う例題としてよく出てきたりするように、総和計算は一見簡単そうですが、実はどのように難しいのか、という点を書いてみます。

まず、対象が整数であれば、大きな問題はありません。昔のようにintが16ビットの場合は、160*160=25600 でぎりぎりに近く 200*200=40000 ではもう 32767 を超えて溢れますから、intではなくlongを使うといった注意が、以前は必要だったというくらいでしょうか。

一方、対象が浮動小数点の総和は、場合によってはそう簡単ではありません。

場合として、まず、符号が正か負の片方だけであれば簡単です(代表的なものとしては内積など)。ソートして絶対値順に並べ、絶対値が小さい側の端2個のペアを取り出して、その和を計算し、結果をソートされている列の入るべき場所に挿入する、という操作を繰り返せば、基本的には問題はありません。

符号が両方ある場合は、正と負に振り分けてそれぞれ計算し、最後に差をとれば良い、と思うかもしれませんが、それではうまくない場合があります。極端な場合として、正側と負側のそれぞれの合計の絶対値が、2倍以内という近い値になってしまうかもしれません。そうなると桁落ちになります。

桁落ちという現象は、しばしば誤解が見られますが、それ自身は誤差を発生させません。正確には、絶対誤差は増えないが、値が小さくなるために相対誤差が(場合によっては文字通り「桁違いに」)大きくなる、という現象です。

そういったような場合、その絶対誤差は、そこに至るまでの計算過程での情報落ちによる誤差の積み残しの集積になっています。

直感的には、桁落ちの英語が「キャンセル」であるように、総和をとる対象中の、正負それぞれの絶対値の大きい値どうしでキャンセルできるものがあれば、それぞれでキャンセルすれば、「桁落ちは起きているが、情報は失われていない」という状態を維持できるので、それを繰り返してゆけば、正確な計算ができるはずです。

しかし、そのようなヒューリスティック的な計算をいちいちやっていては、総和計算に期待されるような O(n) に近い効率はとても実現できませんから、実際に提案されている手法は、何らかの方法で積み残しを全部残すであるとか、倍精度浮動小数点で表現可能な値の範囲全体をカバーする巨大な固定小数点で計算するとか、そういった手法になっています。