programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

# Iterative Fibonacci Method Problem

Ranch Hand
Posts: 72
• Number of slices to send:
Optional 'thank-you' note:
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.

Sheriff
Posts: 11343
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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 ]

Wanderer
Posts: 18671
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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.

Sheriff
Posts: 22701
129
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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.

author
Posts: 4335
39
• Number of slices to send:
Optional 'thank-you' note:
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: 22701
129
• Number of slices to send:
Optional 'thank-you' note:

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: 22701
129
• Number of slices to send:
Optional 'thank-you' note:
http://mathworld.wolfram.com/FibonacciNumber.html contains the direct funtion:

 The harder I work, the luckier I get. -Sam Goldwyn So tiny. - this ad: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising