# Fibonacci Sequence Problem

Sam Benry
Ranch Hand
Posts: 89
Trying to solve this problem
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

wrote this code, but as always... the code is never returning an answer ...
donno why though, any help would be appreciated.

marc weber
Sheriff
Posts: 11343
Originally posted by Sam Benry:
...the code is never returning an answer...

You can add some code to the end of your while loop to display progress...

This will show you that your code runs very slowly, so waiting for it to reach 4000000 will require a bit of patience.

To test the logic during development, you might want to lower your end point. For example, enter a modest 10 rather than 4000000.
[ March 22, 2008: Message edited by: marc weber ]

Sam Benry
Ranch Hand
Posts: 89
i must find a faster, more efficient way to do it... anyone has any ideas?

Paul Clapham
Sheriff
Posts: 21443
33
Are the Fibonacci numbers randomly odd and even, or is there a pattern there?

marc weber
Sheriff
Posts: 11343
Your cumulative sum probably needs to be a BigInteger, because this gets big fast. But the numbers in the sequence itself all fit nicely into type int, and that would mean less object creation/manipulation.
[ March 22, 2008: Message edited by: marc weber ]

marc weber
Sheriff
Posts: 11343
Originally posted by marc weber:
Your cumulative sum probably needs to be a BigInteger, because this gets big fast...

Whoops, I need to take that back.

I based this on output from running a modified version of your code, but after thinking about it, that's just not right. Adding even numbers in the sequence that don't exceed 4 million is one thing. But adding even numbers from the first 4 million in the sequence is quite another.

[ March 22, 2008: Message edited by: marc weber ]

Sam Benry
Ranch Hand
Posts: 89
yea it should...but it doesnt.... its SO SLOW
test it and see
but I cant figure out why.. its only 1 loop to 4 million....

Sam Benry
Ranch Hand
Posts: 89
the loop takes more than 1h 30min to finish
I started the program and it didnt finish yet

Sam Benry
Ranch Hand
Posts: 89
I gave up
I started the program on 2:53:32
and now it is 5:15
and still no result
Why is it taking this much? is it an infinite loop?

Campbell Ritchie
Sheriff
Posts: 50666
83
That is an unusual Fibonacci series; the commonest series starts with 1, 1, 2, 3. Its 10th member is not 89, but 55.
The sum of all Fibonacci numbers in that series F1 + F2 + F3 . . . Fn = F(n+2) - 1.
Fibonacci numbers in that series run odd-odd-even-odd-odd-even. You should be able to prove that easily from simple addition.
Suggest you use a long rather than a BigInteger; you won't run out of space before 4000000. You can probably actually get away with an int. You can get the first 46 members of that Fibonacci series into an int without overflow, and the first 92 into a long. At least that is what happened when I tried it a few months ago as far as I remember.

You can work out the nth member of the common Fibonacci series by calculating round(phi^n/sqrt5) where phi is the Golden ratio (1.618... = (1+sqrt5)/2) and sqrt5 is the square root of 5 and round means round to the nearest whole number.

A quick way to work out whether a number is odd or even is to use the bitwise and operator: if(x & 1 == 0). . . or if(x & 1 != 0). . .

You are comparing the number of iterations i with the last term of 4000000, which means you will iterate approx 4000000 times, rather than finding the last Fibonacci number before 4000000. You will have your app running for years like that!

You can Google for Fibonacci algorithms. There is one in Anne Kaldewaij, Programming : the derivation of algorithms (Prentice Hall International series in computer series) Hemel Hempstead : Prentice Hall International, 1990, ISBN 0132041081, I think page 98, which runs in logarithmic time, but that is really complicated.

You will also find the standard recursive algorithmBut this is given as an example of exponential complexity; if you count the number of iterations it turns out to be 2Fn - 1, and its complexity is O(1.618^n). Ouch. It can take ages to run. But since 4000000 is above the 31st Fibonacci number in that series and below the 32nd, even that is not too bad.

It is quite easy to write a Fibonacci algorithm which runs in linear time. You have to pass the current Fibonacci number and the previous one and add them. You end up with a method with this sort of signature: public long fibonacci(long current, long previous, int count).

Write that, get it running, test it. Marc Weber is right; it will produce a result in a few milliseconds. Then create a sum variable, and put a statement in the fibonacci method to add to sum if the value is an even number.

Easy-peasy. And did you get the prime numbers thing to work?

Garrett Rowe
Ranch Hand
Posts: 1296
The problem isn't your algorithm as marc pointed out. The problem is your misreading of the problem. The problem is looking for the sum of all even fibonacci numbers less than 4000000. Your program is attempting to take the first 4000000 fibonacci numbers and sum the even ones. Your program will end in a flash when you make that change.
[ March 23, 2008: Message edited by: Garrett Rowe ]

Campbell Ritchie
Sheriff
Posts: 50666
83
Actually, I think you ahve got a linear complexity Fibonacci algorithm there. I hadn't read it properly. Sorry , and well done .

Guy Allard
Ranch Hand
Posts: 776
Here is gory stuff on Fibonacci numbers.

Yes, there is a pattern to even and odd numbers.

As written, I think that code will produce erroneous results for any value of n, such that:

Try it with just n == 11, and check the result by hand. The fix for that seems to be:

marc weber
Sheriff
Posts: 11343
Originally posted by marc weber:

And won't need any BigIntegers, by the way.

Sam Benry
Ranch Hand
Posts: 89
This is resulting in negative though it is BigInteger

Sam Benry
Ranch Hand
Posts: 89
and I found this code

which seems pretty simple but I cant figure out how to display the numbers, for example if I want to display the first 10 values in the sequence, how can I do that using this code?

Campbell Ritchie
Sheriff
Posts: 50666
83
Originally posted by Sam Benry:
This is resulting in negative though it is BigInteger
That is a linear complexity non-recursive Fibonacci algorithm. Put in a for loop rather like this:
for(int i = 0; i < 50; i++)
System.out.printf("The %dth Fibonacci number is %d.%n" i, fib1(i));

and you should get
The 0th Fibonacci number is 0.
The 1th Fibonacci number is 1.
The 2th Fibonacci number is 1.
The 3th Fibonacci number is 2.
The 4th Fibonacci number is 3.
The 5th Fibonacci number is 5
etc etc.

Try adding && fibA < 4000000 to the middle part of the heading of your for loop, then it ought to stop at 4000000.

Campbell Ritchie
Sheriff
Posts: 50666
83
Originally posted by Sam Benry:
and I found this code

which seems pretty simple but I cant figure out how to display the numbers, for example if I want to display the first 10 values in the sequence, how can I do that using this code?
That is the exponential complexity Fibonacci recursive algorithm; it is virtually identical to what I quoted earlier. In all the computer science books as an example of an inefficient use of recursion. Don't use it.

Your problem, which people have already told you about, is the middle part of your for-loop. YOu know I said to add "fibA < 4000000"? Well delete the bit about k < n. That means you are not going on until the Fibonacci number reaches 4000000, ie about 31-32 passes. What you are actually doing is organising 4000000 passes which will give you a result about 1.627477199E835950. If you are lucky your JVM will crash before you get to 8 million digits.

To display the numbers from this 2nd algorithm, use exactly the same for-loop as in my post of 10 minutes ago. Remember the 0th number should be 0 and the 1th(!) and 2th(!) should both read 1.
And Marc Weber is correct. You can do everything with int arithmetic and not bother with BigIntegers.

Sam Benry
Ranch Hand
Posts: 89
Im not looking to count them, I want their sum (the sum of the even valued) which is turning out to be a HUGE number... unless Im doing something wrong

Sam Benry
Ranch Hand
Posts: 89
okey problem solved

but I have a question, why must the loop terminate when FibA < 4000000 not when k < 4000000
I still dont get it

Garrett Rowe
Ranch Hand
Posts: 1296
Carefully reread the problem. It says, the sum of all even Fib numbers less than 4000000, not the sum of the even Fib numbers from fib(1) to fib(4000000). As Campbell and marc both tried to point out, the fib numbers start exceeding 4000000 at about fib(31). You were looping about 3,999,969 more times than you needed to.

Sam Benry
Ranch Hand
Posts: 89
hehe
I get it now
thanks everybody

Campbell Ritchie
Sheriff
Posts: 50666
83
Originally posted by Sam Benry:
hehe
I get it now
thanks everybody
You're welcome.

Greenhorn
Posts: 12
Here's my solution :

Rob Spoor
Sheriff
Posts: 20707
68

arturo orozco
Greenhorn
Posts: 1
Anup Jadhav wrote:Here's my solution :

why you check if fibonacci is divisible by 2?? i don't understand =S