CODEWITHSUNDEEP
javaalgorithmdebuggingfibonacci
Jodast
Jodast

Reputation: 1299

Why do I get a negative output when I run my program to compute the sum of all even Fibonacci numbers?

Background:

I'm working on Project Euler problem #2 and I have a class built to solve the problem. For those who haven't done this before, this is the problem:

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.

The problem:

I have the program built to solve the problem given, but when I run it, I get the value -1833689714. This should not be the value returned, as I sum only positive numbers and no multiplications are performed that I know of. How do I fix this?

My code

import java.util.ArrayList;

class Main {
  public static void main(String[] args) {

    int answer = resultsSum(fibonacci(4000000));
    System.out.println(answer);

  }

  public static int resultsSum(ArrayList<Integer> resultList){

    int total = 0;
    for(Integer r : resultList){

      total += r.intValue();

    }

    return total;

  }

  public static ArrayList<Integer> fibonacci(int n){

    ArrayList fibEvens = new ArrayList<Integer>();
    int a = 1;
    int b = 2;
    fibEvens.add(b);

    for(int i = 1; i < (n - 1); i++) {

      int tempVar = a;
      a = b;
      b += tempVar;
      if(b % 2 == 0){

        fibEvens.add(b);

      }
    }
    return fibEvens;
  }
}

https://projecteuler.net/problem=2

Upvotes: 0

Views: 294

Answers (3)

bathudaide
bathudaide

Reputation: 747

Because

  • int data type stores number from -2^31 to 2^31 - 1
  • Integer data type stores number from -2^63 to 2^63 - 1

Try with BigInteger 

public static BigInteger fibonacci(int n) {
    BigInteger[] f = new BigInteger[n + 1];
    f[0] = BigInteger.ZERO;
    if (n > 0) {
        f[1] = BigInteger.ONE;
    }
    for (int i = 2; i < f.length; i++) {
        f[i] = f[i - 1].add(f[i - 2]);
    }
    return f[n];
}

But the 4 million Fibonacci value very long. See more 300th, 500th

Upvotes: 1

Daekard
Daekard

Reputation: 171

The reason you're getting a negative result is that the the terms of the Fibonacci sequence above the 88th term are in excess of the maximum positive value of the Long data type in java, which is 9,223,372,036,854,775,80.

When you attempt to increment the long data type beyond it's max value by one it wraps around to the minimum value (-9,223,372,036,854,775,80). At the point the Fibonacci terms exceed the max value, you're doing this many times over.

Additionally, the problem you've posted indicates that you should be stopping when the value of the number derived from the sequence is greater than 4 million, not trying to add the even values of the first 4 million values (which is huge).

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

It looks like your code is attempting to get to the 4-millionth Fibonacci number, which is quite different than the terms in the Fibonacci sequence whose values do not exceed four million.

Upvotes: 2

Related Questions