# Homework Help: Java: Fibonacci Sequence

1. May 13, 2015

### Robben

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. May 13, 2015

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

3. May 13, 2015

### Robben

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?

4. May 13, 2015

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

5. May 13, 2015

### Robben

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

6. May 13, 2015

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

7. May 14, 2015

### gabbagabbahey

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?

8. May 14, 2015

### 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
Code (Text):
array[i] = array[i - 2] + array[i - 1];

9. May 14, 2015

### 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

Last edited: May 14, 2015
10. May 14, 2015

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

11. May 14, 2015

### 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:

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

12. May 15, 2015

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