フィボナッチ数とひまわり

Ruby

最近何かと話題のフィボナッチ数計算の高速化ですが、

  F(n)  =  (fib(n+1), fib(n))    （2次元の縦ベクトルだが表記の都合で横に書く）
  A  =  ((1, 1), (1, 0))         （第1行が(1, 1)で第2行が(1, 0)の行列）

　すると，F(n) = A F(n-1) = A A F(n-2) = A A A F(n-3) = ...となるから，F(n)を計算するためには，Aのn乗を計算して，それに右からF(0)をかければ良いことになる。

計算量の工夫でプログラムは劇的に速くなる

以前この記事を読んだときも、ははー、と思ったのですが、そのときは実装してみなかったのでちょっと実装してみました。

require "matrix"

def fib(n)
  aux = proc do |m, a|
    case m
    when 0 then Matrix.I(2)
    when 1 then a
    else aux[m % 2, a] * aux[m / 2, a * a]
    end
  end
  (aux[n, Matrix[[1, 1], [1, 0]]] * Vector[1, 0])[1]
end

p (0...10).map {|n| fib(n) }
p fib(1000)

元のアイデアそのままの実装です。

$ time ruby t.rb
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
434665576869374564356885276750406258025646605173717804024817
290895365554179490518904038798400792551692959225930803226347
752096896232398733224711616429964409065331879382989696499285
16003704476137795166849228875

real    0m0.051s
user    0m0.044s
sys     0m0.008s

はやーい。


全然関係ないですが、

ヒマワリの種の数をらせんに沿って数えてゆくとフィボナッチ数があらわれる。

フィボナッチ数 - Wikipedia

だそうで、へー、って感じです。数えられる気がしないけど。フィボナッチ数と黄金角が関係するのかな。

そういうのを考えるのは苦手なので、とりあえず絵だけ作ってみました。どこかで見たことあると思ったら定番の弾幕ですね。クリックしたら大きいの出ます。

require "cairo"

S, L = 250, 1000

surface = Cairo::ImageSurface.new(Cairo::FORMAT_ARGB32, S * 2, S * 2)
context = Cairo::Context.new(surface)
context.matrix = Cairo::Matrix.new(S, 0, 0, S, S, S)

context.set_source_rgb(1, 1, 1)
context.rectangle(-1, -1, 2, 2)
context.fill

a = 0
L.times do |i|
  a = (a + 2 * Math::PI * fib(i) / fib(i + 1)) % (2 * Math::PI)
  r = i.to_f / L
  x, y = r * Math.cos(a), r * Math.sin(a)
  context.set_source_rgb(0, 0, 0)
  context.circle(x, y, (0.05 + r) / 20)
  context.fill
end

surface.write_to_png("sunflower.png")

これで正しいのかどうかは不明。フィボナッチ数を使う必要はなく、黄金角の整数倍をとっていくべきな気もする。あとアフィン変換はいつも試行錯誤してしまう (関係ない) 。


で、このひまわりをちょっといじったらなんだかキモイのができました。脈動とか螺旋とか。クリックしたら大きくなります。


とりとめのない日記でした。