aspose file tools*
The moose likes Beginning Java and the fly likes Iterative Fibonacci Method Problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Iterative Fibonacci Method Problem" Watch "Iterative Fibonacci Method Problem" New topic
Author

Iterative Fibonacci Method Problem

Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
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.


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

Joined: Aug 31, 2004
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);


"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
marc weber
Sheriff

Joined: Aug 31, 2004
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

Joined: Feb 05, 2005
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

Joined: Feb 05, 2005
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

Joined: Aug 31, 2004
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

Joined: Aug 31, 2004
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

Joined: Jan 30, 2000
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.


"I'm not back." - Bill Harding, Twister
Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
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

Joined: Oct 27, 2005
Posts: 19759
    
  20

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Greg Roberts
Ranch Hand

Joined: Feb 05, 2005
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

Joined: Oct 23, 2005
Posts: 3716
    
    5

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?


My Blog: Down Home Country Coding with Scott Selikoff
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19759
    
  20

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

Joined: Oct 27, 2005
Posts: 19759
    
  20

http://mathworld.wolfram.com/FibonacciNumber.html contains the direct funtion:
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Iterative Fibonacci Method Problem