"Takaaki Tateishi" <ttate / kt.jaist.ac.jp> wrote in message
news:200208081557.g78FvQWN029329 / smtp16.dti.ne.jp...
> Hello,
>
> I introduce an extension module called ruby-optimizer:
>
>   http://www.ruby-lang.org/en/raa-list.rhtml?name=Optimization+Modul
>
> The implementation is rough and I don't exactly understand how to
construct
> a node tree. However, today I've successfuly optimize tail recursion
> automatically using the module. In this mail, I introduce a script
'fact.rb'
> and its result. The script has two versions of the factorial function
which
> is defined as follows:

Great!!! - This ought to become a part of the standard libray at
some point IMO.

Here are is the benchmark for the picture perfect candidate of tail
recursion ...

-------
                                       user      system          total
real
fib(29)                     8.773000   0.000000   8.773000 (  9.254000)
fib_tail(29)              0.000000   0.000000   0.000000 (  0.015000)
fib_no_rec(15000)   0.391000   0.020000   0.411000 (  0.429000)
fib_tail(15000)         0.981000   0.040000   1.021000 (  1.053000)
15000.fib_tail           0.992000   0.050000   1.042000 (  1.085000)
-------





----
require 'optimizer'
require 'benchmark'
include Benchmark

def fib_tail(n)
  __fib_tail (0, 1, n)
end

def __fib_tail(cur, suc, rem)
  if rem > 0
    __fib_tail(suc, cur + suc, rem - 1)
  else
    cur
  end
end

# Class based

class Integer
  def fib_tail
    __fib(0,1)
  end
  protected
  def __fib(cur,suc)
    if self > 0
      (self-1).__fib(suc,cur+suc)
    else
      cur
    end
  end
end

def fib(n)
  if n < 2
    n
  else
    fib(n-1) + fib(n-2)
  end
end

def fib_no_rec(n)
  if n < 2
    n
  else
    cur ,suc = 0,1
    n.times {
      tmp = suc
      suc = cur + suc
      cur = tmp
    }
    cur
  end
end

10.times { |n|
 [fib_tail(n), n.fib_tail, fib_no_rec(n)].each {|f|
  raise "bad" unless fib(n) == f
 }
}


bmbm { |x|
  x.report("fib(29)")           { fib(29) }
  x.report("fib_tail(29)")      { fib_tail(29) }
  x.report("fib_no_rec(15000)") { fib_no_rec(15000) }
  x.report("fib_tail(15000)")   { fib_tail(15000) }
  x.report("15000.fib_tail")    { 15000.fib_tail }
}
---


/Christoph