1. Member
Join Date
Feb 2015
Posts
67
Rep Power
0

## 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. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

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

 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. Member
Join Date
Feb 2015
Posts
67
Rep Power
0

## Re: Fibonacci Sequence

Originally Posted by pbrockway2
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.

 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. Member
Join Date
May 2015
Location
Netherlands
Posts
39
Rep Power
0

## 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. Member
Join Date
Feb 2015
Posts
67
Rep Power
0

## Re: Fibonacci Sequence

Originally Posted by Artemia
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. Member
Join Date
May 2015
Location
Netherlands
Posts
39
Rep Power
0

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

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

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

## 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. ## Re: Fibonacci Sequence

Originally Posted by develoSapiens
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

#### Posting Permissions

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