• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Fibonacci Sequence Problem

 
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i must find a faster, more efficient way to do it... anyone has any ideas?
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Are the Fibonacci numbers randomly odd and even, or is there a pattern there?
 
marc weber
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
the loop takes more than 1h 30min to finish
I started the program and it didnt finish yet
 
Sam Benry
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually, I think you ahve got a linear complexity Fibonacci algorithm there. I hadn't read it properly. Sorry , and well done .
 
Ranch Hand
Posts: 776
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is resulting in negative though it is BigInteger
 
Sam Benry
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hehe
I get it now
thanks everybody
 
Campbell Ritchie
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

You're welcome.
 
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's my solution :



btw the answer is: 4613732.
 
Sheriff
Posts: 22783
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't think Sam is still looking for a solution.
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Anup Jadhav wrote:Here's my solution :



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

btw the answer is: 4613732.

 
Rob Spoor
Sheriff
Posts: 22783
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Because the original problem only needed the even values added.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic