Recursion and Ruby

ruby-talk
22

(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.
# Binet's Fibonacci Number Formula -- from Wolfram MathWorld

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.
# Binet's Fibonacci Number Formula -- from Wolfram MathWorld

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)

···

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.

23

Sorry if I misplaced my reply, it was intended for OP and did not in any way
concern what you have said or done, neither reply to your questions, yes I
have definitely chosen the wrong message to reply.
Sorry for the confusion.
Cheers
Robert

···

On 7/13/06, Erik Veenstra <erikveen@gmail.com> wrote:

> Try CachedProc

I could easily implement a cache myself, even a cleaner one
(see below), but that's not my point. My point is: Why is a
lambda call much slower then a method call?

24

(stupid question): what have you used to parse the code and show the nodes?

./alex

···

--
.w( the_mindstorm )p.

On 7/13/06, Dominik Bathon <dbatml@gmx.de> wrote:

On Thu, 13 Jul 2006 15:35:33 +0200, Erik Veenstra <erikveen@gmail.com> > wrote:

>> > ----------------------------------------------------------------
>> >
>> > Version 1 100,0%
>> > Version 2 90,3%
>> > Version 3 72,7%
>> > Version 4 70,2%
>> >
>> > ----------------------------------------------------------------
>>
>> Actually version 3 and version 4 are exactly equivalent for
>> Ruby, it parses them both as NODE_IF:
>
> Well, _finally_ the AST is the same. But somehow, it's
> slower... Maybe the translation from source/syntax to AST is
> slower?
>
> The numbers don't lie. They are averages of 3 test runs, with a
> standard deviation of almost zero. (see below for the full
> results.)

Indeed you are right, I forgot the newline nodes:

>> pp <<code.parse_to_nodes.transform(:keep_newline_nodes => true)
if a
   b
else
   c
end
code
[:newline,
  {:next=>
    [:if,
     {:body=>[:newline, {:next=>[:vcall, {:mid=>:b}]}],
      :else=>[:newline, {:next=>[:vcall, {:mid=>:c}]}],
      :cond=>[:vcall, {:mid=>:a}]}]}]
=> nil

vs.

>> pp "a ? b : c".parse_to_nodes.transform(:keep_newline_nodes => true)
[:newline,
  {:next=>
    [:if,
     {:body=>[:vcall, {:mid=>:b}],
      :else=>[:vcall, {:mid=>:c}],
      :cond=>[:vcall, {:mid=>:a}]}]}]
=> nil

The newline nodes are basically no-ops but they still slow things down a
bit.

In Ruby 1.9 there are no more newline nodes, so there it really is
equivalent.

Dominik

25

"Robert Dober" <robert.dober@gmail.com> writes:

···

On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:

Given you have an reasonably exact approximation of the square root of 5,
this can be done O(1)...

I challange this, as there is no algorithm to compute c**n in O(1) it is
O(log n).

OT, but...

http://mathforum.org/library/drmath/view/52686.html

-Doug

26

From: Glenn Cadman
Sent: Friday, July 14, 2006 10:50 AM

> BTW How would I then access $fib to puts an output of the
sequence eg. 0
> 1 1 2 3 5 8 13 etc.

The best I could do was something like:

printf("Enter a number: ")
i = gets
puts "The #{i.to_i} Fibonacci number is #{fib(i.to_i)} "
0.upto(i.to_i){|k| printf(" #{$fib[k]}") }

maybe

···

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

print "Enter a number: "

i = gets.to_i

puts "The #{i} Fibonacci number is #{fib[i]}"
puts (0..i).map{|k| fib[k]}.join(' ')
----------------------------------------------

cheers

Simon

27

When I am confused (which happens all too often), I like to "see" what
is happening. Below is the same algorithm with a slightly different
implementation (I used class variables rather than a global). I also
provided a simple accessor to the class variable.

Good Luck
pth

class Integer
  @@fib = Hash.new do |h,k|
    puts "Calculate fib[#{k}]"
    h[k] = h[k-2] + h[k-1]
  end

  @@fib[0] = 0
  @@fib[1] = 1

  def fib
    @@fib[self]
  end

  def self.fibs
    @@fib
  end
end

puts 10.fib
puts 7.fib.fib
p Integer.fibs

----- Output ------
Calculate fib[10]
Calculate fib[8]
Calculate fib[6]
Calculate fib[4]
Calculate fib[2]
Calculate fib[3]
Calculate fib[5]
Calculate fib[7]
Calculate fib[9]
55
Calculate fib[13]
Calculate fib[11]
Calculate fib[12]
233
{5=>5, 11=>89, 0=>0, 6=>8, 12=>144, 1=>1, 7=>13, 13=>233, 2=>1, 8=>21,
3=>2, 9=>34, 4=>3, 10=>55}

···

On 7/14/06, Glenn Cadman <glenn.cadman@gmail.com> wrote:
> The problem for
> me is that I find it difficult to understand what is happening in this
> code.

28

http://rubynode.rubyforge.org/

29

sqrt(5)), right?
which is O(?) ?
:wink:

···

On 7/14/06, Douglas McNaught <doug@mcnaught.org> wrote:

"Robert Dober" <robert.dober@gmail.com> writes:

> On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:
>>
>> Given you have an reasonably exact approximation of the square root of
5,
>> this can be done O(1)...
>
> I challange this, as there is no algorithm to compute c**n in O(1) it is
> O(log n).

OT, but...

Classroom Resources - National Council of Teachers of Mathematics

-Doug

which means that you have to compute 2**n (2 is an approximation of

30

fr simon:
# puts (0..i).map{|k| fib[k]}.join(' ')

cool. only one puts speeds things up.

31

sqrt(5) can be pre-computed.

-- Elliot Temple

···

On Jul 13, 2006, at 3:48 PM, Robert Dober wrote:

On 7/14/06, Douglas McNaught <doug@mcnaught.org> wrote:

"Robert Dober" <robert.dober@gmail.com> writes:

> On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:
>>
>> Given you have an reasonably exact approximation of the square root of
5,
>> this can be done O(1)...
>
> I challange this, as there is no algorithm to compute c**n in O(1) it is
> O(log n).

OT, but...

Classroom Resources - National Council of Teachers of Mathematics

-Doug

which means that you have to compute 2**n (2 is an approximation of

sqrt(5)), right?
which is O(?) ?

32

>>
>> "Robert Dober" <robert.dober@gmail.com> writes:
>>
>> >>
>> >> Given you have an reasonably exact approximation of the square
>> root of
>> 5,
>> >> this can be done O(1)...
>> >
>> > I challange this, as there is no algorithm to compute c**n in O
>> (1) it is
>> > O(log n).
>>
>> OT, but...
>>
>> Classroom Resources - National Council of Teachers of Mathematics
>>
>> -Doug
>>
>> which means that you have to compute 2**n (2 is an approximation of
> sqrt(5)), right?
> which is O(?) ?

sqrt(5) can be pre-computed.

obviously my didactic powers are limited :frowning:

In order to compute f(n), you need to compute sqrt(5)**n, which is O(log
n).

Cheers
Robert

-- Elliot Temple

···

On 7/14/06, Elliot Temple <curi@curi.us> wrote:

On Jul 13, 2006, at 3:48 PM, Robert Dober wrote:
> On 7/14/06, Douglas McNaught <doug@mcnaught.org> wrote:
>> > On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:
Curiosity Blog – Elliot Temple

--
Deux choses sont infinies : l'univers et la bêtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein