ruby と python で FloatやRational の和を取る。速さと正確さ。

Float や Rational の合計を求める計算の速度と値を比較する。

https://qiita.com/angel_p_57/items/24078ba4aa5881805ab2#comment-3001a8f9ccbbfd44e719

や

https://twitter.com/angel_p_57/status/1066164125036756993

を受けて。

ruby 2.5  で `inject(&:+)` と `sum` の比較。
ついでに python も。
せっかく python なので、numpy も参戦して。

この記事を公開したら
https://twitter.com/WniKwo/status/1066249059097165824
という反響を頂いたので、`math.fsum` も追加。

コメント欄を受けて numo/narray も参加。

#試したコード

## ruby(sum)

```ruby:ruby2.5
require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.sum }
```

## ruby(sum, Rational)

```ruby:ruby2.5
require "benchmark"

N=100000000
a=[0.00000001r]*N
p Benchmark::realtime{ p a.sum }
```

## ruby(inject)

```ruby:ruby2.5
require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.inject(&:+) }
```

## ruby(inject-no-amp)

コメントを受けて「`&:+`」ではなく「`:+`」にしたバージョン

```ruby:ruby2.5
require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.inject(:+) }
```

## ruby(numo/narray)

```ruby:ruby2.5
require "numo/narray"
require "benchmark"

N=100000000
a=Numo::DFloat.new(N).fill(0.00000001)
p Benchmark::realtime{ p a.sum }
```
(コメント欄に書いていただいたコードそのまま）


## python(sum)

```python:python3.7.1
import time

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( sum(a) )
t1 = time.time()
print( t1-t0 )
```
## python(reduce)

```python:python3.7.1
import time
from functools import reduce

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( reduce(lambda x, y: x + y, a) )
t1 = time.time()
print( t1-t0 )
```

## python(numpy.sum)

```python:python3.7.1
import numpy as np
import time

N=100000000
a = np.array([0.00000001]*N)
t0 = time.time()
print( np.sum(a) )
t1 = time.time()
print( t1-t0 )
```

## python(math.fsum)

```python:python3.7.1
import time
import math

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( math.fsum(a) )
t1 = time.time()
print( t1-t0 )
```


# 実行結果

|処理系|値|時間|
|:--|:--:|:--:|
|ruby(sum)|1.0|0.41秒|
|ruby(sum, Rational)|(1/1)|28.18秒|
|ruby(inject)|1.0000000022898672|5.76秒|
|ruby(inject-no-amp)|1.0000000022898672|3.61秒|
|ruby(numo/narray)|1.0000000022898672|0.12秒|
|python(sum)|1.0000000022898672|0.45秒|
|python(reduce)|1.0000000022898672|8.07秒|
|python(numpy.sum)|0.9999999999997999|0.095秒|
|python(math.fsum)|1.0|1.77秒|

# で。

ruby の `sum` で使われている [カハンの加算アルゴリズム](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%8F%E3%83%B3%E3%81%AE%E5%8A%A0%E7%AE%97%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0) は強力で、わりと正確な値になる感じっぽい。

こんな

```ruby:ruby2.5
Array.new(10000){|x| x*0.0001}.sum #=> 4999.5
Array.new(10000){|x| x*0.0001}.inject(&:+) #=> 4999.499999999991

Array.new(10000){|x| 9.0/(x%5+1)**2}.sum #=> 26345.0
Array.new(10000){|x| 9.0/(x%5+1)**2}.inject(&:+) #=> 26345.000000000713

Array.new(10000){|x| 1.0/1.5**x }.sum #=> 3.0
Array.new(10000){|x| 1.0/1.5**x }.inject(&:+) #=> 2.9999999999999987

Array.new(10000){|x| 1.0/(-1.5)**x }.sum #=> 0.6
Array.new(10000){|x| 1.0/(-1.5)**x }.inject(&:+) #=> 0.5999999999999999

Array.new(10000){|x| (2.0/3)**x}.sum #=> 2.9999999999999996
Array.new(10000){|x| (2.0/3)**x}.inject(&:+) #=> 2.9999999999999987
Array.new(10000){|x| (2.0/3)**x.to_r}.sum.to_f #=> 2.9999999999999996
```

感じ。
ruby の `sum` は不思議なくらい計算が合う。
`(2.0/3)**x` の例は一見誤差があるように見えるが、`(2.0/3).to_r**x` と同じ結果になっていることから分かる通り、`sum` の計算結果は合っているようだ。恐ろしい。

数十例試してみたが、`(hoge)` の `sum` と、`(hoge).to_r` の `sum.to_f` で値に違いがある例は見つけられなかった。
すごい。

一方。
python の `sum()` は普通に足し算しているだけのようで、ruby の `inject(&:+)` と全く同じ値になる。

そう思うと `numpy` の `sum` が違う値になるのは謎だけど、原因については調査していない。

速さでは、さすがの numpy様の圧勝。
正確さで圧倒的一位の`Rational` 版は、やっぱり圧倒的に遅かった。

Go とか C++ も参戦させようかとも思ったけど、今日のところはこれぐらいで。

--- 以下追記 ---

python の `math.fsum()` は、ruby の `sum` と同じように誤差の少ない計算をできるみたい。 
see https://docs.python.jp/3/library/math.html#math.fsum

前掲の wikipedia には
「Pythonの標準ライブラリには fsum という総和関数があり、Shewchukのアルゴリズムを使い丸め誤差の蓄積を防いでいる。」とあるので、ruby とはちょっと違う方法みたい。

計算に要する時間は ruby の `sum` よりだいぶ遅い感じ。4倍ちょっと。

そう思うと逆に。
ruby にもやや不正確だけど `sum` よりも速い合計計算メソッドがあってもいいような気がする。

そして。

ruby の `sum` / `inject(&:+)` に課したのと同じような計算を `math.fsum()` / `sum()` に課すと、以下のようになった：

```python:python3.7.1
import math

a=[x*0.0001 for x in range(0,10000)]
print( math.fsum(a) ) #=> 4999.5
print( sum(a) ) #=> 4999.499999999991

a=[9.0/(x%5+1)**2 for x in range(0,10000)]
print( math.fsum(a) ) #=> 26345.0
print( sum(a) ) #=> 2.9999999999999987

a=[1.0/1.5**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 3.0
print( sum(a) ) #=> 2.9999999999999987

a=[1.0/(-1.5)**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 0.6
print( sum(a) ) #=> 0.5999999999999999

a=[(2.0/3)**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 2.9999999999999996
print( sum(a) ) #=> 2.9999999999999987
```

`math.fsum()` は、ruby の `sum` と同じように正確。

--- 以下、さらに追記 ---

コメントの指摘を受けて「`inject(&:+)`」を「`inject(:+)`」に変えたバージョンも試してみたところ、実行時間が6割ちょっとになった。すごい。なんだこれ。

さらに。

ruby の numo/narray の `sum` が参戦。
速度面では python の `numpy.sum` に肉薄するものの惜しくも敗れた。

値のほうは `inject(&:+)` などと同じ値になった。ますます `numpy.sum` だけが別の値になっているのが目立っている。