From: Robert Klemme <shortcutter@...>
Date: 2006-05-29T16:36:56+09:00
Subject: Re: Fast Fibonacci method

2006/5/29, C Erler <erlercw@gmail.com>:> On 28/05/06, Robert Klemme <shortcutter@googlemail.com> wrote:> >> > btw, did you try the iterative approach with results stored in an Array or> > Hash?>> I can't make the previous code iterative without difficulty, because it> isn't tail-recursive.  Someone on #ruby-lang gave me a relatively-quick> tail-recursive method, but making it iterative made it slower.
This is the usual iterative solution:
class Integer  # not thread safe!  @@fib = [0, 1]
  def fib    for i in @@fib.length .. self      @@fib << @@fib[i - 1] + @@fib[i - 2]    end    @@fib[self]  endend
With a little more effort you can limit array size to two and preventthe error I was seeing:
>> 1_000_000.fib(irb):7:in `+': failed to allocate memory (NoMemoryError)        from (irb):7:in `fib'        from (irb):6:in `fib'        from (irb):13:in `irb_binding'        from /usr/lib/ruby/1.8/irb/workspace.rb:52:in `irb_binding'        from ⊂:0
:-))
>  I think Ruby> (1.8.2) is trying to trick us into using functional programming or> something.
Ruby is generally not good at recursion.  Some hope this improves with 2.0.
Kind regards
robert
-- Have a look: http://www.flickr.com/photos/fussel-foto/