Ruby 2.4 の新機能, Array#sum

Ruby 2.4 で追加されている新機能のひとつに Array#sum があります。

(参: ドキュメントは http://ruby-doc.org/core-2.4.0_rc1/Array.html#method-i-sum

共立『アルゴリズム辞典』でも「総和計算」を立項しているように、情報落ち*1*2による「積み残し」が場合によっては著しいのが、対象が浮動小数点の時の総和計算の問題点です。

Array#sum は、Kahan summation algorithm(wikipedia:カハンの加算アルゴリズム、summation なので -総和アルゴリズム ないし -総和計算アルゴリズム、としたほうが訳としては正確)の改良版などの手法を実装しており、かなりの高精度な結果が得られます。

次のようなスクリプトで試してみると(実験に適した浮動小数点乱数を生成するため、拙作の RandomFloat を使用)、

# sum sample
require_relative 'random_float'

r_f = RandomFloat.new gt:1, lt:2**38

loop {
  arr = []
  (1000000).times {
    x = r_f.rand
    arr << x
    arr << -x
  }
  arr.shuffle!
  p arr.sum
}

そこそこ過酷な条件の総和計算ですが、次のように、ほぼ正確な結果を得られています(完全に正確ではない結果も、時折出ています)。

$ ruby-trunk -v sum_sample.rb
ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-freebsd10.3]
0.0
0.0
0.0
0.0
0.0
-1.3322676295501878e-15
0.0
1.4654943925052066e-14
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

Python の math.fsum との違い

ネットを捜すと、Python の math.fsum との関連で議論されていることがありますが、両者は基本的なコンセプトの点で別物です。今回実装された Array#sum は、あくまでも「高精度」であり、誤差が発生する可能性自体はあります。一方(現在の?)Python の math.fsum は、たとえて言うなら、入力や途中の計算を全て Rational に変換してから行い(実際の実装は異なります*3)、最後に浮動小数点に戻したような「正確」な結果を返すもので、前述で見たような誤差が発生することはありません。

もしそのような「正確な総和」が Ruby でどうしても必要な場合は、Rational を使ってユーザが実装すれば良いでしょう。そのような sum も(私見では、現在の sum と別の実装として、違う名前でメソッドを追加すべきだと思っています)もしかしたら今後実装されるかもしれません(関連するチケットは存在しています)。

*1:正負の要素があると、桁落ちが発生することもありますが、総和計算における主要な問題は桁落ちではありません。むしろ、正しく計画された桁落ちであれば情報は欠けないのであり、情報が積み残されて消えてしまった、という「結果が露呈する(ことがある)」のが、総和計算における桁落ちです。

*2:この桁落ちに関しては、以前のPythonのドキュメントの和訳に、原文には相当するcancellationという語は実のところ無いのですが、手違いにより「桁落ち」という表現があったため、誤解している人ももしかしたらいるかもしれません。

*3:色々な手法が提案されています。