```On Jul 14, 2006, at 4:32 AM, Glenn Cadman wrote:

> Daniel Martin wrote:
>> "Erik Veenstra" <erikveen / gmail.com> writes:
>>
>>> You could use "case" as well (see version 2). It's faster.
>>> Using an ordinary if..else (without the elsif part) is faster
>>> (see version 3). And version 4 is once again faster.
>>>
>>> 4 is faster than 3 is faster than 2 is faster than 1...
>>
>> All of these suffer from the problem that they make approximately
>> fib(n)
>> function calls to compute fib(n).  Why not remember the value of
>> fib(n) the ruby way, with a Hash that computes it naturally?
>>
>> \$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
>> \$fib[0] = 0
>> \$fib[1] = 1
>>
>> def fib(n)
>>   \$fib[n]
>> end
>>
>> This will be faster, and O(n), rather than O(fib(n)).  Also note that
>> the base cases of 0 and 1 are handled simply and declaratively
>> without
>> messing up the main body of the code.
>>
>> (Of course, now someone will respond with one of the O(log(n))
>> algorithms for computing fib(n))
>
> Well whilst my orginal exercise was just to get recursion working in
> ruby, I have to say this solution is very quick to calculate any
> result
> and is recursive in a way that is quite "foriegn" to me. The
> problem for
> me is that I find it difficult to understand what is happening in this
> code. I would have though the stack would collapse due to referencing
> something that is not defined yet. eg.  h[k-2] for example in the
> intial
> state of the \$fib hash would not be found unless the k was 3 or 2. eg
> \$fib(30) would return "I dont have any thing to reference for h[30] =
> h[28] + h[29], has h[28] and h[29] havent been defined.
>
> BTW How would I then access \$fib to puts an output of the sequence
> eg. 0
> 1 1 2 3 5 8 13 etc.

(I hate when the email doesn't get through)

I first saw this Hash trick in a RubyQuiz solution.  I've used it in
different ways since, but here's some amazing evidence as to it's power:

I ran the comparisons locally to try things out.  Basically, you just
can't beat memoization with a Hash for something this simple (it's
so that they produced the same sequence: fib(0) = 0, fib(1) = 1, fib
(2) = 1, fib(3) = 2, etc.  (Some of them had fib(0) == fib(1) == 1)

100.times { 0.upto(30) { |n| fib(n) } }
user     system      total        real
fib1.rb: if        682.070000   1.850000 683.920000 (689.604829)
fib2.rb: case      631.260000   1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000   0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000   0.470000 499.230000 (499.626195)
fib6.rb: Hash        0.000000   0.000000   0.000000 (  0.007612)
fib7.rb: formula     0.030000   0.000000   0.030000 (  0.023598)
fib8.rb: BigMath     2.750000   0.010000   2.760000 (  2.762493)

user     system      total        real
fib1.rb: if        100.000 %    1.850000 683.920000 (689.604829)
fib2.rb: case       92.550 %    1.380000 632.640000 (636.994644)
fib3.rb: simple if  75.178 %    0.860000 513.630000 (515.151776)
fib4.rb: simple ?:  73.124 %    0.470000 499.230000 (499.626195)
fib6.rb: Hash        0.000 %    0.000000   0.000000 (  0.007612)
fib7.rb: formula     0.004 %    0.000000   0.030000 (  0.023598)
fib8.rb: BigMath     0.403 %    0.010000   2.760000 (  2.762493)

Let's peel those fast ones apart a bit:

10_000.times { 0.upto(30) { |n| fib(n) } }
user     system      total        real
fib6.rb: Hash      0.240000   0.000000   0.240000 (  0.246511)
fib7.rb: formula   2.610000   0.010000   2.620000 (  2.635959)
fib8.rb: BigMath 302.950000   0.810000 303.760000 (306.202394)

What about when the numbers get bigger? Does the formula start to

1000.times { 0.upto(300) { |n| fib(n) } }
user     system      total        real
fib6.rb: Hash      2.310000   0.010000   2.320000 (  2.322534)
fib7.rb: formula  45.720000   0.090000  45.810000 ( 46.018314)

Uh, not really.

Let's see them all together again:

fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user     system      total        real
fib1.rb: if        6158.150000   3.740000 6161.890000 (6167.126104)
fib2.rb: case      5702.300000   5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000   3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000   5.540000 4974.870000 (4986.140834)
fib6.rb: Hash        0.020000   0.000000   0.020000 (  0.021521)
fib7.rb: formula     0.240000   0.000000   0.240000 (  0.245543)
fib8.rb: BigMath    27.740000   0.040000  27.780000 ( 27.828623)

==> fib.rb <==
require 'benchmark'
include Benchmark

require '../constantize.rb'

fibsto = ENV['FIBS_UPTO'] || 30
fibrep = ENV['FIB_REPTS'] || 1000

algorithms = [ ]
Dir.glob(ARGV.empty? ?
'fib[1-46-9].rb' :
ARGV.each { |p| Regexp.quote(p) }.unshift('{').push
('}').join(%{,})) do |f|

require f
mod = constantize(File.basename(f,'.rb').capitalize)
include mod
algorithms << Hash[ :description => "#{f}: #{mod.module_eval
{ description }}",
:alg => lambda { fibrep.times { 0.upto(fibsto)
{ |n| mod.fib(n) } } },
:fib => lambda { |n| mod.fib(n) }
]
end

algorithms.each do |a|
fibsto.upto(fibsto) do |n|
puts "#{a[:description]} for #{n}: #{a[:fib].call(n)}"
end
end

puts "#{fibrep}.times { 0.upto(#{fibsto}) { |n| fib(n) } }"
bm(1 + algorithms.inject(9) { |mx,h| mx<h[:description].length ? h
[:description].length : mx }) do |x|
algorithms.each do |a|
x.report(a[:description]) { a[:alg].call }
end
end

==> fib1.rb <==
# VERSION 1
module Fib1
def description; "if"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
if n == 0
return 0
elsif n == 1
return 1
else
return fib(n-1) + fib(n-2)
end
end
end

==> fib2.rb <==
# VERSION 2
module Fib2
def description; "case"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
case n
when 0
0
when 1
1
else
fib(n-1) + fib(n-2)
end
end
end

==> fib3.rb <==
# VERSION 3
module Fib3
def description; "simple if"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
if n<=1
n.zero? ? 0 : 1
else
fib(n-1) + fib(n-2)
end
end
end

==> fib4.rb <==
# VERSION 4
module Fib4
def description; "simple ?:"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
n<=1 ? (n.zero? ? 0 : 1) : fib(n-1) + fib(n-2)
end
end

==> fib5.rb <==
# Version 5
module Fib5
def description; "lambda"; end

fib = lambda{|n|
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
n<=1 ? (n.zero? ? 0 : 1) : fib[n-1] + fib[n-2]
}
end

==> fib6.rb <==
# Version 6
module Fib6
def description; "Hash"; end

\$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
\$fib[0] = 0
\$fib[1] = 1

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
# puts "#{File.basename(__FILE__,'.rb')}(#{n}) => #{\$fib[n]}" if
n == 30
\$fib[n]
end
end

==> fib7.rb <==
# Version 7
# Weisstein, Eric W. "Binet's Fibonacci Number Formula." From
MathWorld--A Wolfram Web Resource.
# http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

module Fib7
def description; "formula"; end

SQRT5 = Math.sqrt(5)
def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
(((1+SQRT5)**n - (1-SQRT5)**n)/(2**n * SQRT5)).round
end
end

==> fib8.rb <==
# Version 8
# Weisstein, Eric W. "Binet's Fibonacci Number Formula." From
MathWorld--A Wolfram Web Resource.
# http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

require 'bigdecimal'
require 'bigdecimal/math'
include BigMath

module Fib8
def description; "BigMath"; end

SQRT5 = BigMath.sqrt(BigDecimal("5"),20)
def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
(((1+SQRT5)**n - (1-SQRT5)**n)/(2**n * SQRT5)).round.to_i
end
end

==> ../constantize.rb <==
# from Jim Weirich (based on email correspondence)
def constantize(camel_cased_word)
camel_cased_word.
sub(/^::/,'').
split("::").
inject(Object) { |scope, name| scope.const_get(name) }
end

==> timing.txt <==
user     system      total        real
fib1.rb: if        682.070000   1.850000 683.920000 (689.604829)
fib2.rb: case      631.260000   1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000   0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000   0.470000 499.230000 (499.626195)
fib6.rb: Hash        0.000000   0.000000   0.000000 (  0.007612)
fib7.rb: formula     0.030000   0.000000   0.030000 (  0.023598)
fib8.rb: BigMath     2.750000   0.010000   2.760000 (  2.762493)

user     system      total        real
fib1.rb: if        100.000 %    1.850000 683.920000 (689.604829)
fib2.rb: case       92.550 %    1.380000 632.640000 (636.994644)
fib3.rb: simple if  75.178 %    0.860000 513.630000 (515.151776)
fib4.rb: simple ?:  73.124 %    0.470000 499.230000 (499.626195)
fib6.rb: Hash        0.000 %    0.000000   0.000000 (  0.007612)
fib7.rb: formula     0.004 %    0.000000   0.030000 (  0.023598)
fib8.rb: BigMath     0.403 %    0.010000   2.760000 (  2.762493)

10_000.times
user     system      total        real
fib6.rb: Hash      0.240000   0.000000   0.240000 (  0.246511)
fib7.rb: formula   2.610000   0.010000   2.620000 (  2.635959)
fib8.rb: BigMath 302.950000   0.810000 303.760000 (306.202394)

0.upto(300)
user     system      total        real
fib6.rb: Hash      2.310000   0.010000   2.320000 (  2.322534)
fib7.rb: formula  45.720000   0.090000  45.810000 ( 46.018314)

fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user     system      total        real
fib1.rb: if        6158.150000   3.740000 6161.890000 (6167.126104)
fib2.rb: case      5702.300000   5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000   3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000   5.540000 4974.870000 (4986.140834)
fib6.rb: Hash        0.020000   0.000000   0.020000 (  0.021521)
fib7.rb: formula     0.240000   0.000000   0.240000 (  0.245543)
fib8.rb: BigMath    27.740000   0.040000  27.780000 ( 27.828623)

```