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 ]

"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

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

i must find a faster, more efficient way to do it... anyone has any ideas?

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 ]

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.

If I'm reading the problem correctly, your code should run in the blink of an eye. [ March 22, 2008: Message edited by: marc weber ]

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

the loop takes more than 1h 30min to finish I started the program and it didnt finish yet

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

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?

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?

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 ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40515

28

posted

0

Actually, I think you ahve got a linear complexity Fibonacci algorithm there. I hadn't read it properly. Sorry , and well done .

Originally posted by marc weber: ...If I'm reading the problem correctly, your code should run in the blink of an eye...

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

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

This is resulting in negative though it is BigInteger

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

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

Joined: Oct 13, 2005
Posts: 40515

28

posted

0

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

Joined: Oct 13, 2005
Posts: 40515

28

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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

Joined: Jan 17, 2006
Posts: 1296

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

hehe I get it now thanks everybody

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40515

28

posted

0

Originally posted by Sam Benry: hehe I get it now thanks everybody