Why are you interested in the millionth Fibonacci number, actually ?

on 2006-05-28 20:53

on 2006-05-28 21:30

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.

on 2006-05-28 23:16

btw, did you try the iterative approach with results stored in an Array or Hash? robert

on 2006-05-29 03:42

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.

on 2006-05-29 04:01

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.

on 2006-05-29 09:37

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

on 2006-05-29 11:21

> @@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