Results 1 to 9 of 9
  1. #1
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Fibonacci Sequence

    I am not sure what is wrong with my code? The code produces a negative number when I type in 4000000 into the fib method parameter.


    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, ...

    By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.


    Java Code:
    public static void fib(int k) {
        
        int result = 0;
        int[] array = new int[k];
        array[0] = 1;
        array[1] = 2;
         
        for (int i = 2; i < k; i++) {
            array[i] = array[i - 2] + array[i - 1];       
        }
         
        for (int even: array) {
             System.out.print(even + " ");
             if (even % 2 == 0) {
                 result += even;
             }
        }        
        System.out.println(result);
    }

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,716
    Rep Power
    18

    Default Re: Fibonacci Sequence

    The code produces a negative number when I type in 4000000 into the fib method parameter.
    An array of 4 million elements is large but probably won't explode your computer. But, how big (roughly) do you expect the 4 millionth fibonacci term to be? (and why?) The point is that ints have some maximum size; if you exceed that Bad Things will happen.

    [Edit] I've just read the question as given to you! You aren't supposed to sum every second of the first 4 million terms, you are supposed to sum the even valued terms whose values are less than 4 million. That's quite different and there won't be anything like 4 million of them. If you answer the questions above you will get some idea of how many there might be. Not that it matters much, you could use a for loop and "break" when the value of the Fibonacci term exceeds 4 million.
    Last edited by pbrockway2; 05-14-2015 at 04:21 AM.

  3. #3
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Fibonacci Sequence

    Quote Originally Posted by pbrockway2 View Post
    An array of 4 million elements is large but probably won't explode your computer. But, how big (roughly) do you expect the 4 millionth fibonacci term to be? (and why?) The point is that ints have some maximum size; if you exceed that Bad Things will happen.

    [Edit] I've just read the question as given to you! You aren't supposed to sum every second of the first 4 million terms, you are supposed to sum the even valued terms whose values are less than 4 million. That's quite different and there won't be anything like 4 million of them. If you answer the questions above you will get some idea of how many there might be. Not that it matters much, you could use a for loop and "break" when the value of the Fibonacci term exceeds 4 million.
    But my math is correct. For small amount of numbers it works but not for large amounts. I even rewrote it to:

    Java Code:
    public void fib(int k) {
    		
    		int sum = 0;
    		int term1 = 1;
    		int term2 = 2;
    		int term3 = 0;
    		int i = 2;
    		
    		while (i < k) {
    			
    			term3 = term1 + term2;
    			
    			term1 = term2;
    			term2 = term3;
    			i++;
    			
    			if (term2 % 2 == 0) {
    				sum += term2;
    			}
    		}
    		
    		System.out.println(term3);
    		System.out.println(sum + 2);
    		
    	}
    which also didn't work.

  4. #4
    Artemia is offline Member
    Join Date
    May 2015
    Location
    Netherlands
    Posts
    39
    Rep Power
    0

    Default Re: Fibonacci Sequence

    if I understand the question correctly, aren't you supposed to add all the even valued terms as long as they are less than 4 million?
    meaning that you don't need 4 million iterations of the loop but stop the loop once term 3 reaches a value higher than 4 million.

    if that's not it, maybe try finding out at which point the loop starts giving weird results and use the debugger to figure out what goes wrong and why there.
    (from what I can tell the code seems to be right if you just want it to do an assigned number of iterations, I'm not a pro though so not sure how much my opinion is worth :P )

  5. #5
    Robben is offline Member
    Join Date
    Feb 2015
    Posts
    67
    Rep Power
    0

    Default Re: Fibonacci Sequence

    Quote Originally Posted by Artemia View Post
    if I understand the question correctly, aren't you supposed to add all the even valued terms as long as they are less than 4 million?
    meaning that you don't need 4 million iterations of the loop but stop the loop once term 3 reaches a value higher than 4 million.

    if that's not it, maybe try finding out at which point the loop starts giving weird results and use the debugger to figure out what goes wrong and why there.
    (from what I can tell the code seems to be right if you just want it to do an assigned number of iterations, I'm not a pro though so not sure how much my opinion is worth :P )
    Oh wow, no wonder! Thank you!

  6. #6
    Artemia is offline Member
    Join Date
    May 2015
    Location
    Netherlands
    Posts
    39
    Rep Power
    0

    Default Re: Fibonacci Sequence

    You're very welcome :)
    I used to have this problem in math, they ask questions in such a way that it's easily misunderstood.
    Hope you managed to complete the assignment :)

  7. #7
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Fibonacci Sequence

    Pbrockway2 told you the same thing earlier. He also told you that ints have a maximum value. To be more specific, signed values use the high-order bit as the sign bit. If it is set, the number is negative. This means you can increment a positive value until it becomes negative. Try this example:

    Java Code:
    int a = Integer.MAX_VALUE-10;
    for (int j = 0; j < 20; j++) {
          System.out.println(a++);
    }
    So to solve your problems like this, switch to longs or use BigInteger. You may also want to read up on 2's complement math. It is a fundamental concept in computer science.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  8. #8
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,716
    Rep Power
    18

    Default Re: Fibonacci Sequence

    I don't know whether it works with big numbers
    The limitation to the size of number you can represent with some finite (and, as numbers go, rather small) number of bits will remain. That's what motivated my questions.

    Just for fun I wrote out the first dozen or so terms of the Fibonacci sequence and decided how many bits "wide" they were. As jim829 points out the leftmost bit is used for the sign but leaving that detail aside, the resulting sequence of "bit sizes" is bad news for any attempt to represent the Fibonacci sequence with primitive values. And the exercise does provide an answer to my questions.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Fibonacci Sequence

    Quote Originally Posted by develoSapiens View Post
    It is not erlang, where recursion don't need extra big part from memory.
    Erlang is no magic: it either also uses a large stack for recursive functions (methods) or it can use a large memo for its memozation of those recursive functions. (for the recursive fibonacci function it uses n slots in its memo table where n is the largest parameter value of the function; but an ordinary stack uses n slots also).

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

Similar Threads

  1. Fibonacci sequence using Dynamic Arrays
    By MylesPollie in forum New To Java
    Replies: 6
    Last Post: 02-17-2014, 04:26 PM
  2. need some help doing loops with fibonacci sequence
    By barqcider in forum New To Java
    Replies: 6
    Last Post: 09-25-2013, 11:03 PM
  3. Replies: 1
    Last Post: 01-23-2013, 06:06 PM
  4. Fibonacci Sequence Problem
    By Zigster in forum New To Java
    Replies: 10
    Last Post: 07-06-2012, 09:54 PM
  5. Fibonacci sequence
    By ŖΫ ỏ Ңόρę in forum New To Java
    Replies: 6
    Last Post: 03-25-2010, 06:59 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •