Jonathan Gnagy's Blog

Rails for everyone!

Recursive Ruby meets Fibonacci

I was trying out recursive programming in Ruby the other day. I figured a good way to try it out was using a pretty well known mathematical sequence called the Fibonacci sequence. In math, the sequence is defined as

Fn = Fn – 1 + Fn – 2

with seed values of

F0 = 0 and F1 = 1

so its a prime candidate for a recursive algorithm in Ruby. I started off with a working, but very slow, method that looks like this:

1
2
3
4
5
6
7
8
9

def fib(n)
  if (n == 0)
    return 0 
  elsif (n == 1)
    return 1
  else
    return fib(n - 2) + fib(n - 1)
  end
end

For the first few numbers in the sequence this method performs well enough, but as the number gets larger, things start slowing way down. For example:

1
2
3
4
5

fib 6  #=> 8
fib 9  #=> 34
fib 20 #=> 6765
fib 30 #=> 832040 (took about 5 seconds to complete)
fib 40 #=> ? (waited for over a minute with CPU pegged...)

So, obviously this stuff is working, but its not really very practical. Next I took a stab at using an array to create an in-memory cache, which sped things up immensely:

1
2
3
4
5
6
7
8
9
10
11
12
13

@@cache = [] # this is an in-memory cache
def fib_cached(n)
  if @@cache[n]
    return @@cache[n] # return the cached value, if it exists
  else
    if (n == 0) || (n == 1)
      @@cache[n] = n
    else
      @@cache[n] = fib_cached(n - 2) + fib_cached(n - 1)
    end
    return @@cache[n] # always put the value in cache, then return it
  end
end

This speed difference was unbelievable:

1
2
3
4
5
6
7

fib_cached 6   #=> 8
fib_cached 9   #=> 34
fib_cached 20  #=> 6765
fib_cached 30  #=> 832040
fib_cached 40  #=> 102334155
fib_cached 99  #=> 218922995834555169026
fib_cached 300 #=> 222232244629420445529739893461909967206666939096499764990979600

I tried different numbers up to 999 and wasn’t able slow it down at all, which is great.

Finally, I found a shortcut on a blog (which I can’t remember the URL for), that uses the Golden Ratio (phi) to very quickly find numbers in the Fibonacci sequence. It works very well, but I think since I’m not really using Ruby’s more advanced math modules, the numbers skew a little (then a lot) as the sequence number gets large.

1
2
3
4
5
6

module Math
  Phi = (Math.sqrt(5) + 1) / 2
end
def fib_by_phi(n)
  (((Math::Phi ** n) - ((1 - Math::Phi) ** n) ) / Math.sqrt(5)).to_i
end

Although this was extremely fast, it didn’t quite produce accurate results at higher sequence numbers:

1
2
3
4
5
6
7

fib_by_phi 6   #=> 8
fib_by_phi 9   #=> 34
fib_by_phi 20  #=> 6765
fib_by_phi 30  #=> 832040
fib_by_phi 40  #=> 102334155
fib_by_phi 99  #=> 218922995834555891712
fib_by_phi 300 #=> 222232244629422676106398124069050176556246085874450435841982464

In the end, I found that the cached recursive algorithm was the best balance of speed and reliability, trading off memory for CPU cycles. Here’s some code that you can use to test things and get a very precise measurement of performance:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def stop_watch(&block)
  start_time = Time.now
  puts "Started at #{start_time}"
  begin
    yield
  rescue Exception => e
    puts "Block died: #{e}"
  end
  end_time = Time.now
  puts "Ended at #{end_time}"
  puts "Finished in #{end_time - start_time} seconds."
end
#run each method in a stop_watch
stop_watch do
  puts fib_cached 9999
end
stop_watch do
  puts fib_by_phi 9999
end
Post by Jonathan Gnagy @ 2009-12-03 01:01:33 -0700 Tags: code, fibonacci, math, ruby
Comments:
Add a comment:
Please leave following field blank:
SubmitSubmit    HelpHelp