sum と inject(:+) の結果が違うだと？

まあ知ってる人には驚く話ではないのだけれども。

# Ruby で数値の総和を求める

Ruby で数値の配列が与えられていて，その要素の総和を求めたいとき，[Array#sum](https://docs.ruby-lang.org/ja/2.7.0/method/Array/i/sum.html) を使うのが鉄則である。

以下のコードを比較してみよう。

```rb
numbers = Array.new(1000){ rand }

# (1)
numbers.inject(&:+)

# (2)
numbers.inject(:+)

# (3)
numbers.sum
```

速度は (1) → (2) → (3) の順に速くなる。
これらの中で (3) は最も高速かつ簡素であり，それだけでも `sum` を採用すべき理由になる。
しかし，それだけではない。

# 精度

数値が Integer や Rational の場合はそもそも演算の誤差が生じないのでよいが，数値が Float の場合，演算の誤差を考えなければならない。

浮動小数点数の演算には誤差を伴うことが多い。それ自体は仕方がないのだが，2 回以上演算を繰り返す場合は，誤差の**累積**を問題にしなければならない。

結論を先に書くと，`sum` を採用すべき三つ目の理由は，`sum` には誤差の累積を抑える「Kahan の加算アルゴリズム」が採用されていることである。
参考：[カハンの加算アルゴリズム - Wikipedia](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)


# 誤差の例

## Float が表す数について

本題に入る前に，少し予備知識の整理をしておきたい。

2 進法に基づく浮動小数点数で 0.1 という数値が表せないことはよく知られている。簡単に言えば，0.1 という数値は 2 進法では無限小数になるので，それを有限桁で表すことはできないからである。

では，Ruby で

```rb
puts 0.1
```

を実行すると端末に `0.1` と表示されるのはどういうことか。

まず Ruby の処理系は `0.1` という浮動小数点数リテラルを見て，`Float` オブジェクトを生成する。
これは「0.1 に極めて近いが同じではない」浮動小数点数を表わしている。
大雑把に言って，（10 進で）15 桁くらいの精度をもった数値である。いや，実は Ruby の Float オブジェクトがどんなビット列で表されているかは環境依存なのだが，多くの環境で C 言語の double という数値型に基づいているらしく，その場合はそうなる。本記事の内容はすべてこの前提で書かれており，該当しない環境の場合は結果が異なりうる。

0.1 ではない数値を表示させているのになぜ `0.1` と表示されるのか。
それは，`puts` に Float オブジェクトを与えたとき，まず `to_s` メソッドによって「10 進法に基づく数字列」という String オブジェクトに変換されるのだが，その結果が `"0.1"` という文字列だからである。
10 進 → 2 進と違って，2 進 → 10 進の変換だと，有限小数が無限小数になったりはしない[^go]。実際，浮動小数点数リテラル `0.1` が表す Float オブジェクト（が表す数値）は，10 進法で

[^go]: これは基数 10 が 2 の倍数であることによる。

```
0.1000000000000000055511151231257827021181583404541015625
```
という，小数点以下 55 桁の有限小数になるようだ（私がなんかどこかでミスしてなければ）。
しかし，Ruby の [Float#to_s](https://docs.ruby-lang.org/ja/2.7.0/method/Float/i/inspect.html) メソッドはそんな文字列を返さない。
Float オブジェクトが持ちうる精度に見合った桁数だけを取り，`"0.1"` という文字列を返すのである。これは `to_s` の仕様である。
（このあたり，あまり詳しくないので，誤りの指摘や補足があればお願いします）

（2021-03-07 追記）
@mrkn さんによると Ruby は浮動小数点数を 10 進の文字列に変換するにあたって以下の論文のアルゴリズムを使っているそうです（Slack の [ruby-jp](https://ruby-jp.github.io/) で教えていただきました）。
https://ampl.com/REFS/rounding.pdf
えっと，私はめくってみましたが読んでません（ムツカシソウ）。

## 誤差の累積

では本題である `sum` と `inject(:+)` で結果が異なる例を見よう。

```rb
numbers = [0.1] * 6

puts numbers.sum == numbers.inject(:+)
# => false
```

6 個の `0.1` の総和が一致していない（繰り返すが，環境によっては結果が異なりうる）。
それぞれの結果を `puts` で表示させてみよう。

```rb
numbers = [0.1] * 6

puts numbers.sum        # => 0.6000000000000001
puts numbers.inject(:+) # => 0.6
```

これを見て，「えっ？　`sum` より `inject(:+)` のほうが精度が高いじゃん！　嘘つき！」と早合点してはいけない[^ten]。

[^ten]: 10 個の 0.1 を足し合わせた結果を `puts` して `sum` のほうが精度が高いと説明しているサイトがあるが，これも妥当でない。

既に見たように Ruby の浮動小数点数リテラル `0.1` によって生成される Float オブジェクトが表している数値は 0.1 ではないのである。
ちなみに，`inject` 版の結果が `0.6` と表示されているが，返り値が 0.6（という数を表す Float オブジェクト）であることを意味しない。あくまで返り値を `to_s` した結果が `"0.6"` という文字列だというだけである。

## 誤差の評価

では，誤差がどうなっているかを正確に知るにはどうすればいいか。
それには [Float#to_r](https://docs.ruby-lang.org/ja/2.7.0/method/Float/i/to_r.html) を用いて Float オブジェクトを Rational オブジェクトに変換する。
このメソッドは，Float が表している数値に厳密に一致する有理数オブジェクトを返す。

こんな具合である。

```rb
puts 0.1.to_r
# => 3602879701896397/36028797018963968
```

なんかスゴイ分数が表示されたが，何かの間違いではない。
`0.1` というリテラルに基づく `Float` オブジェクトはこのような数値を表しているのである。
一見わけが分からない数字列に見えるが，よくよく見えば分子と分母は末尾以外は数字が一致しており，分子のほうが一桁少ない。つまり，0.1 という数値に非常に近いことが見て取れる。

Rational に持ち込めば加減乗除で演算誤差は生じない。
こんなふうにしよう。
Rational にしてから取った総和を「真の和」と呼ぶことにする。
`sum` と `inject` で作った和と真の和の差**の絶対値**を「誤差」と呼ぶことにする。
どちらが誤差が小さいか比べるため，`sum` 版の誤差から `inject` 版の誤差を引いたものを計算する。これが正なら `sum` 版の誤差が大きく，負なら `inject` 版の誤差が大きい。

```rb
# 足すべき数
x = 0.1

# 足し合わせる個数
n = 6

# 真の和（Rational）
exact_sum = x.to_r * n

# n 個の x からなる配列
numbers = [x] * n

# sum による和（Rational）
sum_by_sum = numbers.sum.to_r

# その誤差
error_by_sum = (exact_sum - sum_by_sum).abs

# inject による和（Rational）
sum_by_inject = numbers.inject(:+).to_r

# その誤差
error_by_inject = (exact_sum - sum_by_inject).abs

# 比較
puts sum_by_sum - sum_by_inject     # => 1/9007199254740992
puts error_by_sum - error_by_inject # => 0/1
```

あれれ？　`sum` 版の和と `inject` 版の和は確かに微妙に違っているのだが，それぞれの誤差は完全に一致している？
一見不可解だが，何も不思議なことはない。「誤差」を計算するときに絶対値を取っているからこうなる。
`sum` 版と `inject` 版の和は，真の和の**左右に**同じ距離だけ離れて存在しているのだ。和そのものの値は違っているが真の和とのズレ量は同じだったということ。

「ん？　じゃあ，`sum` が `inject` より精度が高いとか言ってたのは嘘だったのかよ」
話を最後まで聞いてほしい[^sho]。

[^sho]: 正直に告白すれば，私自身もこの結果を見て，何かの間違いではないかと一瞬思った。

今の場合，つまり，`0.1`（というリテラルによる Float）を 6 個足し合わせた場合は，精度に違いがなかった。
これは `inject` 版にとって幸運なケースだったということだ。
では，実際に `sum` 版のほうが真の和に近いケースはあるのか。あるいは逆のケースは無いのか。
以下のようにして調べてみよう。
足すべき数は `0.1`（というリテラルによる Float）とし，足し合わせる個数を変えていく。

```rb
x = 0.1

1.upto(100) do |n|
  exact_sum = x.to_r * n
  numbers = [x] * n

  sum_by_sum = numbers.sum.to_r
  error_by_sum = (exact_sum - sum_by_sum).abs

  sum_by_inject = numbers.inject(:+).to_r
  error_by_inject = (exact_sum - sum_by_inject).abs

  puts "%4d %2d" % [n, (error_by_sum <=> error_by_inject)]
end
```

`error_by_sum <=> error_by_inject` は，もし `sum` 版の誤差のほうが大きければ `1` を，その逆であれば `-1` を，同じ誤差の大きさなら `0` を返すはずである。

結果は以下のようになった。

```
   1  0
   2  0
   3  0
   4  0
   5  0
   6  0
   7 -1
   8 -1
   9 -1
  10 -1
  11 -1
  12  0
  13  0
  14  0
  15 -1
  16 -1
  17 -1
  18 -1
  19 -1
  20 -1
  21 -1
  22 -1
  23 -1
  24 -1
  25 -1
  26 -1
  27 -1
  28 -1
  29 -1
  30 -1
  31 -1
  32 -1
  33 -1
  34 -1
  35 -1
  36 -1
  37 -1
  38 -1
  39 -1
  40 -1
  41 -1
  42 -1
  43 -1
  44  0
  45  0
  46 -1
  47 -1
  48 -1
  49 -1
  50 -1
  51 -1
  52 -1
  53 -1
  54 -1
  55 -1
  56 -1
  57 -1
  58 -1
  59 -1
  60 -1
  61 -1
  62 -1
  63 -1
  64 -1
  65 -1
  66 -1
  67 -1
  68 -1
  69 -1
  70 -1
  71 -1
  72 -1
  73 -1
  74 -1
  75 -1
  76 -1
  77 -1
  78 -1
  79 -1
  80 -1
  81 -1
  82 -1
  83 -1
  84 -1
  85 -1
  86 -1
  87 -1
  88 -1
  89 -1
  90 -1
  91 -1
  92 -1
  93 -1
  94 -1
  95 -1
  96 -1
  97 -1
  98 -1
  99 -1
 100 -1
```

見てのとおり，1 個から 100 個までの中に，誤差の大きさが同じだったものが 11 あった。
それ以外はすべて `sum` 版のほうが誤差が小さい。
結局，この実験の範囲では，

* `sum` 版と `inject` 版の誤差が同じケース　→　少数
* `sum` 版のほうが誤差が小さいケース　→　多数
* `sum` 版のほうが誤差が大きいケース　→　無し

であった。
しかし，もちろんこんな簡単な実験の結果を一般化するわけにはいかない。今の私にできるのは，Kahan のアルゴリズムを信じることと，上記の実験の範囲内では期待される結果が得られたことを確認することだけである。

ちなみに，`sum` 版が真の和と一致したものは 7 個あった。このうち，3 個は `inject` 版も一致していた。

# まとめ

総和を得るなら `inject(:+)` ではなく `sum` を使おう。
そのほうが簡素で高速。そして，数値が浮動小数点数の場合は誤差の累積も抑えられる。