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 = 1;
array = 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);
}```  Reply With Quote

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.  Reply With Quote

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.  Reply With Quote

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 )  Reply With Quote

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!  Reply With Quote

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 :)  Reply With Quote

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  Reply With Quote

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.  Reply With Quote

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  Reply With Quote

#### Posting Permissions

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