From: jzakiya@... (Jabari Zakiya)
Date: 2002-04-05T07:53:03+09:00
Subject: Fibonacci Number Generators

Hi, I'm a newbie, coming to Ruby from a 
Forth background (see comp.lang.forth).

I downloaded Ruby 1.6.6 with MSVC to
run on Windows 98 on my 600 Mhz Athlon K-7
machine (cerca December 1999).

I saw this implementation of a Fibonacci
number generator at this site
http://www.bagley.org/~doug/shootout/lang/ruby/

Listing 1.

def fib(n)
    if n < 2 then
	1
    else
	fib(n-2) + fib(n-1)
    end
end

ran it with irb, but it produces incorrect
results. The Fibonacci series should be:

  n  | 0   1   2   3   4   5   6   7   8   9 .....
f(n) | 0   1   1   2   3   5   8   13  21  34.....

but the above code produces

  n  | 0   1   2   3   4   5   6   7   8   9 .....
f(n) | 1   1   2   3   5   8   13  21  34  55.....

As you see, the answers are off by one index.

To correct it, replace the '1' with 'n':

Listing 2.

def fib(n)
    if n < 2 then
	n
    else
	fib(n-2) + fib(n-1)
    end
end

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

Try fib(30) to see what I mean.

Since this is one of the first useful routines
I ever did in Forth, I became quite aware of
this problem. Of course, the solution is to
do it iteratively. The following is a fast iterative
method which produces the correct results.

Listing 3.

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

Inside the def, fib is just a variable, you can rename.

This returns virtually instantaneous answers, even
for fib(1000) [DON'T EVEN TRY THIS RECURSIVELY!! :-( ]

Question for the learned, is there a faster/better way
to code this (syntactical differences aside)?

Jabari