Java Fibonacci Sequence: Finding the Sum of Even-Valued Terms Under 4 Million

[Robben]

Homework Statement

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.

Homework Equations

None

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.

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);
}

 

[scientific601]

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.

 

[Robben]

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.

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?

 

[scientific601]

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.

 

[Robben]

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.

Yup, I changed all the int to long and the method produced a different negative number.

 

[scientific601]

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)

 

[gabbagabbahey]

The code produces a negative number when I type in 4000000 into the fib method parameter.

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?

 

[scientific601]

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

array[i] = array[i - 2] + array[i - 1];

instead of the index.

 

[rcgldr]

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

 

[scientific601]

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.

 

[rcgldr]

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:

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;
}

 

[Mark44]

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.

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