逆数の総和を取る6つの方法とその誤差

これは何？

で素朴に総和をとっていて。

そういえば部分和を積み重ねることで誤差を減らせるよという話を最近 Qiita で見たな

と思い。

足し方でどう誤差が変わるのか調べてみた。

調べたこと

$$
\frac{1}{1} + \frac{1}{2} + \frac{1}{3} +...+ \frac{1}{n}
$$

を、n=100〜5100 についていろいろな方法で計算する。
得られた結果が、真の値を倍精度に丸めたものとどれだけ離れているのかを調べた。

足し方

以下の5通りの足し方を試した。

順に足す

こういうやつ。

ruby

(1..n).each do |ix|
  sum += 1.0/ix
end

逆順に足す

こういうやつ。

ruby

n.downto(1) do |ix|
  sum += 1.0/ix
end

遠くを足して積み重ねる

全体の和を、前半の総和と後半の総和を足すことで求める。
前半の総和は、前半の前半の総和 + 前半の後半の総和で。
後半の総和は、後半の前半の総和 + 後半の後半の総和で。
という感じの再帰呼び出しで求める。

近くを足して積み重ねる

先頭を 0 番目として。
まず、$2i+1$ 番目を $2i$ 番目に加える。
次に、$4i+2$ 番目を $4i$ 番目に加える。
次に、$8i+4$ 番目を $8i$ 番目に加える。
　　︙
　　︙
繰り返していけばそのうち0番目に全体の総和が入っている。

混ぜてから足す

手順は「遠くを足して積み重ねる」とほぼ同じなんだけど、その前にシャッフルする。

sum で足す

ruby の Enumerable には sum という素晴らしいメソッドがある。
不思議な数学の魔力によって、誤差少なめで合計を求めることができるらしい。

こういう風に使う。

ruby

(1..n).sum{ |ix| 1.0/ix }

誤差の評価

有理数で計算した正しい値と、それぞれの方法で計算した値の差の2乗の平均の平方根で評価する。

コード

こんなコードを書いた。

ruby

METHODS = []

METHODS.push def simple(n)
  sum=0
  (1..n).each do |ix|
    sum += 1.0/ix
  end
  sum
end

METHODS.push def reverse(n)
  sum=0
  n.downto(1) do |ix|
    sum += 1.0/ix
  end
  sum
end

def splitsum_impl(v,size)
  return v[0] if size==1
  s=size/2
  l=size-s
  s.times do |ix|
    v[ix] += v[ix+l]
  end
  splitsum_impl(v,l)
end

METHODS.push def split_sum(n)
  splitsum_impl((1..n).map{ |e| 1.0/e },n)
end

def sumnear_impl(v, step)
  return v[0] if v.size<step
  0.step(v.size-1,step*2) do |ix|
    v[ix]+=v[ix+step]||0
  end
  sumnear_impl(v,step*2)
end

METHODS.push def sum_near(n)
  sumnear_impl((1..n).map{ |e| 1.0/e },1)
end

METHODS.push def shuffle_sum(n)
  splitsum_impl((1..n).map{ |e| 1.0/e }.shuffle,n)
end

METHODS.push def use_sum(n)
  (1..n).sum{ |ix| 1.0/ix }
end

def main( lo, len )
  hi = lo+len
  sum=0
  expecteds = (1..hi).each.with_object({}) do |ix,o|
    sum+= 1r/ix
    o[ix]=sum.to_f
  end

  METHODS.each do |m|
    diff2s=[]
    (lo..hi).each do |v|
      sum = self.send(m,v)
      diff2s.push( (sum - expecteds[v])**2 )
    end
    puts("%12s %7.2fe-16" % [ m, (diff2s.sum / diff2s.size)**0.5*1e16] )
  end
end

main(100,5000)

METHODS.push def なんて初めて書いた。

実行結果

ruby 3.0.1 で実行するとこんな感じになった。

      simple  172.03e-16
     reverse   41.35e-16
   split_sum    8.27e-16
    sum_near   10.35e-16
 shuffle_sum    8.21e-16
     use_sum    2.93e-16

結論

いろいろ試したわけじゃないから、これだけで色々言うことは出来ないわけだけど。

• やっぱり sum は優秀。
• 分割して加算してから総和を取るのはわりといい考え。
• 素直に足すとやっぱり誤差が大きい。

ということなのかなと思う。

とはいえ。
sum や分割加算は優秀なんだけど、元の記事にある「総和が N を超えたら加算をやめる」みたいな用途には使えない。

かといって、誤差なしの有理数で計算するには膨大な時間が必要だ。
難しいね。

追記

という記事を別に起こした。