```"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

```