🐌

フィボナッチ数列とメモ化と黄金比

2023/08/21に公開

Ruby

黄金比

フィボナッチ数列

tech

基本形

一般的な公式と言われるようなコードがこれ。

def f(n)
  if n == 0 || n == 1
    return 1
  end
  f(n - 2) + f(n - 1)
end

10.times.collect { |e| f(e) }  # => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

ただマイナスが渡されると死ぬのが気になる。

begin
  f(-1)
rescue SystemStackError => error
  error  # => #<SystemStackError: stack level too deep>
end

比較部分の改善

そこでこう書くと安全になる。

def f(n)
  if n <= 1
    return 1
  end
  f(n - 2) + f(n - 1)
end

f(-1)  # => 1

なぜこんなことをいちいち書くかというと、あとで実行する黄金比を求めるときに -1 を渡してはまったから。

メモ化で速度の改善

自分の環境では N=36 で1秒を超えるようになった。

Benchmark.ms { f(36) }  # => 1360.9830000059446

そこでメモ化すれば速くなる。

def f(n)
  @memo ||= [1, 1]
  @memo[n] ||= f(n - 2) + f(n - 1)
end

再度、速度を検証すると、

Benchmark.ms { f(36) }     # => 0.012999997125007212
Benchmark.ms { f(100) }    # => 0.016999998479150236
Benchmark.ms { f(1000) }   # => 0.2099999983329326
Benchmark.ms { f(10000) }  # => 5.287000007228926

N=36 が一瞬になった。N=1万でも約6ms。

begin
  f(100000)
rescue SystemStackError => error
  error  # => #<SystemStackError: stack level too deep>
end

しかし N=10万でスタックが死んだ。

非再帰化

def f(n)
  @memo ||= [1, 1]
  (2..n).each do |i|
    @memo[i] ||= @memo[i - 2] + @memo[i - 1]
  end
  @memo[n]
end

これで N=10万でも動く。

Benchmark.ms { f(100000) }  # => 243.37899999227375

黄金比の求め方

「今の結果÷一つ前の結果」で求まる。

f(1).fdiv(f(0))  # => 1.0
f(2).fdiv(f(1))  # => 2.0
f(3).fdiv(f(2))  # => 1.5
f(4).fdiv(f(3))  # => 1.6666666666666667
f(5).fdiv(f(4))  # => 1.6
f(6).fdiv(f(5))  # => 1.625
f(7).fdiv(f(6))  # => 1.6153846153846154
f(8).fdiv(f(7))  # => 1.619047619047619
f(9).fdiv(f(8))  # => 1.6176470588235294

float 型の限界まで調べると

(1..100).each_cons(2) do |i, j|
  a = f(i).fdiv(f(i.pred))
  b = f(j).fdiv(f(j.pred))
  if a == b
    p a  # => 1.618033988749895
    p i  # => 40
    break
  end
end

N = 40 までいけた。

最初は 0 なのか 1 なのか？

こちら解答が興味深かった。

要約すると、

本質とは関係ないのでどっちでもいい派
フィボナッチ氏は 1, 1, 2 と書いたので最初は 1 でいいんじゃね？派
0 の方が落ち着く派
自然界に 0 はないので 1 であるべきだ派

個人的には 0 だと落ち着くというのがしっくりくる。