1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Java: Fibonacci Sequence

  1. May 13, 2015 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant equations

    None

    3. The attempt at a solution

    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.

    Code (Java):

    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) {
             
             if (even % 2 == 0) {
                 result += even;
             }
        }        
        System.out.println(result);
    }
     
    Last edited: May 13, 2015
  2. jcsd
  3. May 13, 2015 #2
    Does it work for smaller numbers? If so then your algorithm is correct but you are exceeding the limit of integers. Try long instead of int for all variables.
     
  4. May 13, 2015 #3
    It does work for smaller numbers but for large numbers it doesn't. I tried with long and double and it still produces different negative numbers?
     
  5. May 13, 2015 #4
    You sure? If result is also long... (I said all variables).

    Also I wonder if "find the sum of the even-valued terms" meant you are to find some shortcut formula.
     
  6. May 13, 2015 #5
    Yup, I changed all the int to long and the method produced a different negative number.
     
  7. May 13, 2015 #6
    It may be in the System.out.println statement. Try using formatting and use ll for "long long" sized integers.
    Something like
    System.out.printf("%ll", result)
     
  8. May 14, 2015 #7

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    You may want to re-read the problem statement:)). There is a VERY significant difference between the 4 millionth term in the Fibonacci Sequence and the highest term that does not exceed 4 million: so significant that using long or double can't possibly save you in the case of the former. Try adding a println to print the last term (array[k-1]) to see how quickly the series grows.... compare for example k=10 ,20,30,40....can you imagine how large the 4 millionth term in the sequence must be?
     
  9. May 14, 2015 #8
    You are correct. The OP and I did not read the problem statement carefully.
    The problem statement does not ask to go to the 4 millionth term but the term that does not exceed 4 million.
    So the loop limit should check the value of
    Code (Text):
    array[i] = array[i - 2] + array[i - 1];
    instead of the index.
     
  10. May 14, 2015 #9

    rcgldr

    User Avatar
    Homework Helper

    Fibonacci numbers, fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, ...
    max values for 32 bit signed, unsigned, and 64 bit signed, unsigned integers:

    fib(46) = 1836311903 = hex 6D73E55F
    fib(47) = 2971215073 = hex B11924E1

    fib(92) = 7540113804746346429 = hex 68A3DD8E61ECCFBD
    fib(93) = 12200160415121876738 = hex A94FAD42221F2702

    every 3rd fibonacci number is even (since pattern is even+odd, odd+even, odd+odd)
    fib(0) = 0
    fib(3) = 2
    fib(6) = 8
    fib(9) = 34
    fib(12) = 144
    fib(15) = 610
    fib(18) = 2584
     
    Last edited: May 14, 2015
  11. May 14, 2015 #10
    That's a good observation! Using that sequence according to other sources we only have to go as high as about fib(33) which is well below our integer limits. Anything beyond that and the terms are above 4,000,000 anyway.
     
  12. May 14, 2015 #11

    rcgldr

    User Avatar
    Homework Helper

    On a side note, Fibonacci for negative numbers can be determined by noting:

    fib(i-2) = fib(i) - fib(i-1)

    fib(6) = 8
    fib(5) = 5
    fib(4) = 3
    fib(3) = 2
    fib(2) = 1
    fib(1) = 1
    fib(0) = 0
    fib(-1) = 1
    fib(-2) = -1
    fib(-3) = 2
    fib(-4) = -3
    fib(-5) = 5
    fib(-6) = -8

    You can also calculate fibonacci sequence using only two local variables:

    Code (Text):

    unsigned int fib(unsigned int n)
    {
    unsigned int f0, f1;
        f0 = n & 1;         /* if n even, f0=0=fib(0), f1=1=fib(-1) */
        f1 = 1 - f0;        /* else       f1=0=fib(0), f0=1=fib(-1) */
        switch(n%2){
            do{
                f1 += f0;
              case 1:
                f0 += f1;
              case 0:
                continue;
            }while(0 <= (int)(n -= 2));
        }
        return f0;
    }
     
     
  13. May 15, 2015 #12

    Mark44

    Staff: Mentor

    I'm more familiar with the sizes of types for C and C++ than with Java, but it seems likely to me that a long and an int are the same size (i.e., 32 bits).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted