From: Dave Thomas <Dave@...>
Date: 2002-04-05T08:12:56+09:00
Subject: Re: Fibonacci Number Generators

jzakiya@mail.com (Jabari Zakiya) writes:

> However, because this is using recursion, this
> code is S...L......O................W

To be fair, the Bagley algorithm is designed to be a comparative
performance test, so it is probably intended to exercise recursion.

> def fib(n)
>     if n < 2 then
> 	fib = n	 # for fib(0)=0 & fib(1)=1
>     else
> 	fib = f1 = 0
> 	f2 = 1
> 	(n-1).times do
> 		fib = f1 + f2
> 		f1 = f2
> 		f2 = fib
> 	end
>     end
>     fib
> end
> 
> Question for the learned, is there a faster/better way
> to code this (syntactical differences aside)?

There may well be some number theory here that let's you do amazing
things, but otherwise all I'd do is remove the unnecessary variable:

    def fib1(n)
      return n if n < 2
      f1, f2 = 0, 1
      (n-1).times { f1, f2 = f2, f1+f2 }
      f2
    end


Cheers


Dave