From: Rob Biedenharn <Rob@...>
Date: 2006-07-15T00:57:38+09:00
Subject: Re: Recursion and Ruby

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  
just addition after all).  I did adjust some of the implementations  
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  
have an advantage?

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)