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 |
