rubyで繰り返しの計算処理を高速化させたい。

Question

前提・実現したいこと

初めまして、現在 ruby で一定の整数nを超えるまで規則的に加算を続ける処理を記述しております。
nが２や３など加算の回数が少ない場合は問題ありませんが、１２・１３となるととても時間がかかる為、
計算を高速に出来ないかメモ化や’Memoist’を試してみましたが上手く出来ませんでした。
何か良い方法があればご教授いただけると幸いです。

該当のソースコード

①

@memo = {}

def sum(wer)
  return @memo[[wer]] if @memo[[wer]]
    total = 0
    n = 0
  while total < wer do
    rat = []
      n = n + 1
      denomi = 1..n
      denomi.each do |den|
        r = Rational(1, den)
        rat << r
      end
      total = rat.sum
      @memo[[wer]] = total
  end
    rat.inspect
    rat.last
end

puts sum(15)

②

require 'memoist'
  class Person
    extend Memoist
    def sum(wer)
      n = 0
      i = 0
      while  i < wer
        n += 1
        i = i + Rational(1, n)
      end
      puts n
    end
    memoize :sum
  end

  person = Person.new
  person.sum(15)

試したこと

①では　@memo{}　を使いメモ化をしようとしました。
@memo[[wer]] = total　や、　return @memo[[wer]] if @memo[[wer]]　の位置を試したみたものの変化は感じられませんでした。
②では　Memoist　を導入試しました。

補足情報（FW/ツールのバージョンなど）

ruby 2.5.1
一応整数nは２０ほどを想定しています。

Comments

[ozwk]

S(n)=1+1/2+1/3+...+1/nと整数werに対して
S(n)≧werとなる最小のnを求めたい
みたいな感じで良いんですよね?

[huyusyougun1224]

回答ありがとうございます。
その考え方で合っております。

Answer 1

分母と分子を別計算にしながら、途中でRationalを使って桁数を抑えることで単純な加算より時間は短くなりました。
参考まで。

MAX = ARGV[0].to_i
RAT_NUM = 1070

puts "float simple addition"
sum = 0.0
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  sum += 1.0/n
  if sum > wer then
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum, Time.now-stime)
    wer += 1
  end
end

puts "rational nume/deno addition"
deno = 1
nume = 0
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  nume = nume * n + deno
  deno *= n
  if nume > wer * deno then
    sum = Rational(nume, deno)
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime)
    wer += 1
    nume = sum.numerator
    deno = sum.denominator
  elsif n % RAT_NUM == 0 then
    sum = Rational(nume, deno)
    nume = sum.numerator
    deno = sum.denominator
  end
end

puts "rational simple addition"
sum = Rational(0)
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  sum += Rational(1,n)
  if sum > wer then
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime)
    wer += 1
  end
end

float simple addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.001000
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.001000
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.002002
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.002002
wer= 6, n=       227, sum=6.004366708345567e+00, elapse=0.003019
wer= 7, n=       616, sum=7.001274097134162e+00, elapse=0.003019
wer= 8, n=      1674, sum=8.000485571995782e+00, elapse=0.003993
wer= 9, n=      4550, sum=9.000208062931115e+00, elapse=0.003993
wer=10, n=     12367, sum=1.000004300827578e+01, elapse=0.004990
wer=11, n=     33617, sum=1.100001770863642e+01, elapse=0.006985
wer=12, n=     91380, sum=1.200000305166562e+01, elapse=0.012998
wer=13, n=    248397, sum=1.300000122948093e+01, elapse=0.027957
rational nume/deno addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.000000
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.001030
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.001998
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.001998
wer= 6, n=       227, sum=6.004366708345566e+00, elapse=0.003051
wer= 7, n=       616, sum=7.001274097134161e+00, elapse=0.005050
wer= 8, n=      1674, sum=8.000485571995780e+00, elapse=0.009068
wer= 9, n=      4550, sum=9.000208062931140e+00, elapse=0.030012
wer=10, n=     12367, sum=1.000004300827581e+01, elapse=0.096833
wer=11, n=     33617, sum=1.100001770863643e+01, elapse=0.440332
wer=12, n=     91380, sum=1.200000305166563e+01, elapse=2.853218
wer=13, n=    248397, sum=1.300000122948078e+01, elapse=19.173152
rational simple addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.000997
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.000997
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.001996
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.002991
wer= 6, n=       227, sum=6.004366708345566e+00, elapse=0.003988
wer= 7, n=       616, sum=7.001274097134161e+00, elapse=0.019946
wer= 8, n=      1674, sum=8.000485571995780e+00, elapse=0.030916
wer= 9, n=      4550, sum=9.000208062931140e+00, elapse=0.061500
wer=10, n=     12367, sum=1.000004300827581e+01, elapse=0.295848
wer=11, n=     33617, sum=1.100001770863643e+01, elapse=1.830510
wer=12, n=     91380, sum=1.200000305166563e+01, elapse=12.718921
wer=13, n=    248397, sum=1.300000122948078e+01, elapse=97.580847

Comments

[winterboum]

頑張りましたね

[huyusyougun1224]

回答ありがとうございます。
コードを参考にさせていただいたところかなり速くなったと思います。

重ねてありがとうございました。

Answer 2

ちゃんと検証していないのですが、整数のみの演算にすれば多少は速くなるかもしれません。
（式をミスっていたらごめんなさい）

1 + 1/2 = 1 + 1/2
1 + 1/2 + 1/3 = 1 + (3+2)/(2*3)
1 + 1/2 + 1/3 + 1/4 = 1 + ((3+2)*4+(2*3))/(2*3*4)
1 + 1/2 + 1/3 + 1/4 + 1/5 = 1 + (((3*+2)*4+(2*3))*5)+(2*3*4))/(2*3*4*5)
：
1 + 1/2 + 1/3 + ... + 1/n = 1 + ((A*n)+(n-1)!)/(n!)
1 + 1/2 + 1/3 + ... + 1/(n+1) = 1 + ((B*(n+1))+(n)!)/((n+1)!)

• 次の式の分子のn!は直前の式の分母を使う。
• Bは直前の式の分子((A*n)+(n-1)!)になる。
• 判定は割り算ではなくかけ算（分子 ＜ 分母 × wer）を使う。

Comments

[etsuhisa]

速くないので忘れてください。

[huyusyougun1224]

回答ありがとうございます。
判定を割り算でなく掛け算で行う事は目から鱗でした。上記のコードを参考に少しロジックを変えて試してみようと思います。

[etsuhisa]

恥ずかしい回答にも関わらずコメントありがとうございます。
rationalの方が自前計算より桁数が抑えられるので速かったです。
あと、werが20以下の整数のみであれば、予め計算した値を配列で持っておくのが一番高速だと思いました。

[etsuhisa]

もう一点、rationalを使うなら、1/werで始めて、1/(n×wer)を足し込み、分子が分母以上で判定する方法もあると思います。

[huyusyougun1224]

まだ上手くできてないですが、予め計算した値を配列で持っておくやり方の計算速度は早くなった体感があります。
もう少し頑張ってみます！

Answer 3

規則的に加算　とは
1 + 1/2 + 1/3 + 1/4 + .....
でしょうか。
これですとメモ化はできません。
メモ化は同じ計算を何度も繰り返す場合に有効ですが、この式の場合は「ある計算を繰り返す」って無いですから。

Comments

[huyusyougun1224]

回答ありがとうございます。

はい、加算は　1 + 1/2 + 1/3 + 1/4 + ...　で行っています。
毎回計算式が変わるのでメモ化は出来ないのですね。

メモ化以外の方法で計算速度をあげる事は可能なのでしょうか？

[winterboum]

この数列では、私には思いつきません。
漸化式があればそれを使うのが（精度の吟味は必要ですが）高速化の手ですが、この数列では無いですよね？

[huyusyougun1224]

漸化式であれば 、　a (n+１) ＝　１ / "a（n＋１）"　となりそうですが、　”　”　で囲む部分が分母に当たるので、漸化式として成立するのか解らないです。

計算を行うロジックを考え直した方がいいのでしょうか？

[winterboum]

ごめん、漸化式ではない、なんと言うのかな、この場合　Σ1/n を求める式はないので、概算というか近似式というか。
ロジックですが、
werを越えるのが n だとすると　1/i をn回、+を n回 行うのを減らすロジックを考えないとならないですが、可能？

[huyusyougun1224]

ロジックはお答え頂いた　1/i をn回、+を n回 行うのを減らす　をすぐに思いつくのは難しそうです。

[winterboum]

フィールズ賞ものでしょう

[huyusyougun1224]

そうですよね、森重文先生レベルにはなれないと思うので、少し別の方法や前提条件の見直しをしてみようと思います。