This week's book giveaway is in the OCAJP forum.We're giving away four copies of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) and have Khalid A Mughal & Rolf W Rasmussen on-line!See this thread for details.
Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!

Iterative Fibonacci Method Problem

Greg Roberts
Ranch Hand
Posts: 72
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.

marc weber
Sheriff
Posts: 11343
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);

marc weber
Sheriff
Posts: 11343
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
Posts: 72
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
Posts: 72
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.

marc weber
Sheriff
Posts: 11343
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:

for(int i = 1; i < 7; i++)...

marc weber
Sheriff
Posts: 11343
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 ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671

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.

Greg Roberts
Ranch Hand
Posts: 72
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.

Rob Spoor
Sheriff
Posts: 20608
63
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

Greg Roberts
Ranch Hand
Posts: 72
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.

Scott Selikoff
author
Saloon Keeper
Posts: 4020
18
This is probably irrelevant to the problem at hand, but you do know there's an explicit non-recursive formula to find the nth Fibonacci number?

Rob Spoor
Sheriff
Posts: 20608
63
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):

Rob Spoor
Sheriff
Posts: 20608
63
http://mathworld.wolfram.com/FibonacciNumber.html contains the direct funtion: