I've written a program to compute Fibonacci numbers iteratevely and recursively. The recursive method works fine, but the iterative one is returning bogus numbers. The program also contains code for timing each method.

Here is my code for the iterative method. "int n" is passed into the method and should return the nth term in the Fibonacci sequence.

Greg Roberts<br />CIS Student<br />University of West Florida

Originally posted by Greg Roberts: ... the iterative one is returning bogus numbers...

It looks like it's working fine to me -- except that you're off by one iteration. If I'm not mistaken, the sequence should start with two one's: 1, 1, 2, 3, 5, ... But your method is only generating one one: 1, 2, 3, 5, ...

Note: To see what your method is doing, you might want to put the following line in your loop...

System.out.println("i is " + i + ", and y is " + y);

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer sscce.org

According to Wikipedia - Fibonacci Number, the sequence would be 1, 1, 2, 3, 5, ... starting at n = 1. But it's also defined at n = 0, so you might want to allow for that input as well.

EDIT: Okay, I see that you did allow for n = 0 as a special case. But your code then goes on to calculate the 0th iteration as 1 (the second 1 in the sequence), so it's just starting off on the wrong foot. [ November 19, 2005: Message edited by: marc weber ]

Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72

posted

0

That's strange. I must be calling it wrong. Here's what its computing for me: Fib(3): 5 Fib(13): 610 Fib(23): 75025 Fib(33): 9227465

When the actual Fibonacci numbers are Fib(3): 2 Fib(13): 233 Fib(23): 28657 Fib(33): 3524578

I've taken what the actual numbers should be from here

Here's the complete program:

Try running this and notice the numbers for iteration are different than those from recursion. They should be the same numbers.

Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72

posted

0

Here's something. Instead of computing the Fibonacci numbers 3, 13, 23, 33, its computing the Fibonacci numbers 5, 15, 25, 35. Shouldn't there be something wrong with my method? I'm thinking this because I'm feeding it 3, 13, 23, 33 from the for loop.

Both of your methods are generating the sequence correctly. The problem is that the iterative method is simply returning the wrong number in the sequence. And when n gets large, the output can look way off.

Try these loop parameters to see the difference between your methods:

Originally posted by Greg Roberts: ... Instead of computing the Fibonacci numbers 3, 13, 23, 33, its computing the Fibonacci numbers 5, 15, 25, 35. Shouldn't there be something wrong with my method? ...

Yes, that's exactly what's wrong. The iteration method is returning values that are Fibonacci Numbers (so the algorithm is correct), but they are off by 2 iterations.

(At first, I thought it was only off by 1, but I now see that it's actually off by 2 because your code returns the second "1" for the 0th iteration.) [ November 19, 2005: Message edited by: marc weber ]

I recommend you anyalyze this code carefully. Pretend you are the computer, going through the code line by line. Write down the initial values for each of the variables here, and as you "execute" each line, decide how that will affect the values, and write down the new values after each line. You should gain a deeper understanding of how this code actually works. To paraphrase Inigo Montoya, I do not think this code means what you think it means.

"I'm not back." - Bill Harding, Twister

Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
Posts: 72

posted

0

I changed the algorithm to this:

And it works. Problem is, the algorithm in my discreet mathematics book shows this as:

It looks like this so as to not be language specific. I wasen't exactly sure how to translate this to java, but I'm supposed to use this algorithm. The way I got it working doesn't exactly match the algorithm from the book.

The Pascal program is executing the loop body n - 1 times (1, 2, 3, ..., n-1). The original Java program was executing the loop body n + 1 times (0, 1, 2, ..., n-1, n).

The correct Java translation of the Pascal for loop would be

That's exactly the piece of code that makes it work. Thank you.

I looked a little deeper and found that the pseudocode in the book is listed as "its basic structure resembles that of Pascal, which is currently the most taught programming language."

Is Pascal really that common? Its not even offered at UWF.

Thanks for the help everyone. I modified the program to stop at the 33rd Fib number, but the program actually needs to compute the 43rd as well, I just took it out for the purpose of saving time while I was trying to get it to work. I went back and changed the two loops at the top of the program to:

for(int i = 3; i < 44; i += 10)

For anyone that ran the code, I'm curious how long it takes your computer to compute the 43rd number recursively. It ties up my 3GHz for around 5 minutes! Total of 342,652,542,867 nanoseconds.

Originally posted by Greg Roberts: Is Pascal really that common? Its not even offered at UWF.

When I first started at the Technical University of Eindhoven, The Netherlands, we started in the abstract language GCL (Guarder Command Language) by Dijkstra and Pascal for practicing programming. OOP was tought using Delphi. We didn't get any Java until our 3rd year.

And as Scott said, there is a direct formula for Fibonacci, and also an exponential one. The direct one uses square roots, the exponential one uses matrixes as logic and can be computed as follows (for computing fib(n), n >= 0):