[ruby-core:78518] [Ruby trunk Feature#12871] Using the algorithm like math.fsum of Python for Array#sum

Issue #12871 has been updated by Kenta Murata.


Takeshi Nishimatsu wrote:
> Julia can do it, too.
> 
> ~~~
> julia> sum_kbn([1.0e10, 1.0e-10, -1.0e10])
> 1.0e-10
> ~~~
> 
> The source code is https://github.com/JuliaLang/julia/blob/master/base/reduce.jl .

Thank you for pointing the information.

I referred the paper written by A. Klein [1], and employed the algorithm in that paper.
It is the same algorithm of sum_kbn in Julia.

[1] Klein, A. Computing (2006) 76: 279. http://link.springer.com/article/10.1007/s00607-005-0139-x

----------------------------------------
Feature #12871: Using the algorithm like math.fsum of Python for Array#sum
https://bugs.ruby-lang.org/issues/12871#change-61899

* Author: Keisuke NISHI
* Status: Closed
* Priority: Normal
* Assignee: Kenta Murata
----------------------------------------
Array#sum uses the Kahan's algorithm for Float values now. But it returns inaccurate value in some case like below.

~~~ ruby
# 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
# 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.

~~~ 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
~~~




-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>