Forum: Ruby Re: Fast Fibonacci method

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
67bb4df2775f6a6b603347dce7119571?d=identicon&s=25 unknown (Guest)
on 2006-05-28 20:53
(Received via mailing list)
Why are you interested in the millionth Fibonacci number, actually  ?
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2006-05-28 21:30
(Received via mailing list)
On 28/05/06, Nuralanur@aol.com <Nuralanur@aol.com> wrote:
>
> Why are you interested in the millionth Fibonacci number, actually  ?
>

I just chose a relatively high number to give some comparison of
asymptotic
performance (performance as the input value goes to infinity).  If you
have
an algorithm that loses with low numbers like one million, but starts to
beat the code I gave at some higher input value (and gives perfectly
correct
results without rounding errors), please let me know, since a hybrid of
the
two can be used.
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-05-28 23:16
(Received via mailing list)
btw, did you try the iterative approach with results stored in an Array
or Hash?

robert
E2a9d30a2487a924165aaaa016b54f87?d=identicon&s=25 C Erler (Guest)
on 2006-05-29 03:42
(Received via mailing list)
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?
>
> robert
>

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.  I think
Ruby
(1.8.2) is trying to trick us into using functional programming or
something.

class Integer
  def fib_tail_recursive a=1, b=0, p=1, q=0
    if modulo(2).zero?
      if zero?
        b
      else
        p_p = p*p
        div(2).fib_tail_recursive a, b, p_p + 2*p*q, p_p + q*q
      end
    else
      (self - 1).fib_tail_recursive p*(a + b) + a*q, a*p + b*q, p, q
    end
  end

  def fib_iterative
    n, a, b, p, q = self, 1, 0, 1, 0
    while n.nonzero?
      a, b = p*(a + b) + a*q, a*p + b*q if n.modulo(2).nonzero?
      p_p = p*p
      n, p, q = n.div(2), p_p + 2*p*q, p_p + q*q
    end
    b
  end
end

start_time = Time.now
1_000_000.fib_tail_recursive
p Time.now - start_time
start_time = Time.now
1_000_000.fib_iterative
p Time.now - start_time

This produces the timings (for comparison, the previous fib method takes
about 7 seconds) :
29.297
43.095

I also initially thought you might have meant the standard F[n] = F[n -
1] +
F[n - 2] method with memoization, but it simply gave me more evidence
that
loading Windows XP's task manager from disk only when it's requested is
not
a good idea for those users who need to kill a task that is thrashing
the
disk due to memory exhaustion while their system is frozen for ten
minutes
straight.
E34b5cae57e0dd170114dba444e37852?d=identicon&s=25 Logan Capaldo (Guest)
on 2006-05-29 04:01
(Received via mailing list)
On May 28, 2006, at 9:42 PM, C Erler wrote:

> because it
>      if zero?
>  def fib_iterative
> start_time = Time.now
> 43.095
>

I don't believe it. Really. Ruby doesn't do tail-call optimization,
and even if it did I don't see how the recursive function would be
that much faster than the iterative one. Yet, running the script
myself I get similiar results:
% ruby fib.rb
12.628659
18.508037
logan:/Users/logan/Projects/Ruby Experiments% ruby fib.rb
11.399135
17.393642

Something fishy is going on here.
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-05-29 09:37
(Received via mailing list)
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]
  end
end

With a little more effort you can limit array size to two and prevent
the 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
87e9a89c53ccf984db792113471c2171?d=identicon&s=25 Kroeger, Simon (ext) (Guest)
on 2006-05-29 11:21
(Received via mailing list)
>     @@fib[self]
>   end
> end
>
> With a little more effort you can limit array size to two and prevent
> the error I was seeing:

like

def fib nbr
    a0, a1 = 1, 0
    (nbr-2).times{a1, a0 = a0, a0+a1}
    a0
end

?

But this is way slower than the OPs one.

cheers

Simon
This topic is locked and can not be replied to.