iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

数列の和を計算するアルゴリズム

数列の和の計算にアルゴリズムなんて考える余地はあるのか？と思ったが、誤差についても考える場合、単純な方法以外にも複数のアルゴリズムが存在し使われているということを教えてもらった。

Kahan summation はより高い精度を達成できるが、pairwise summation のほうが高速である。NumPy の sum では pairwise summation algorithm が使われているようだ。

ちなみに、分散を計算する際には専用のアルゴリズムもある。