Project

General

Profile

Actions

Feature #12871

closed

Using the algorithm like math.fsum of Python for Array#sum

Added by labocho (Keisuke NISHI) over 7 years ago. Updated over 7 years ago.

Status:
Closed
Target version:
-
[ruby-core:77771]

Description

Array#sum uses the Kahan's algorithm for Float values now. But it returns inaccurate value in some case like below.

# ruby 2.4.0-preview2
[10000000000.0, 0.0000000001, -10000000000.0].sum #=> 0.0 (expected 0.0000000001)

Python's math.fsum uses another algorithm. It saves all digits, and returns accurate value in such a case.
(See: https://github.com/python/cpython/blob/d267006f18592165ed97e0a9c2494d3bce25fc2b/Modules/mathmodule.c#L1087)

# python 3.5.2
from math import fsum
fsum([10000000000.0, 0.0000000001, -10000000000.0]) #=> 0.0000000001

I propose to use the algorithm like math.fsum of Python for Array#sum.

This is an example implementation in Ruby.

class Array
  # This implementation does not consider non float values
  def sum
    partials = []

    each do |x|
      i = 0
      partials.each do |y|
        x, y = y, x if x.abs < y.abs
        hi = x + y # upper bits
        lo = y - (hi - x) # lower bits (lost)
        if lo != 0.0
          partials[i] = lo
          i += 1
        end
        x = hi
      end
      partials[i..-1] = [x]
    end

    partials.inject(0.0, :+)
  end
end
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0