Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Project Euler #2 Infinity?

Tags:

java

fibonacci

I am trying to solve Euler's Project #2 and I keep getting the answer as "Infinity" or "NaN" (Not a number) I tried changing the type of number to a int (originally Double), but that didn't fix anything just gave me the answer "-1833689714"

public class Pro {
    static int g = 1;
    static int n, f = 0;
    public static void main(String args[]) {
        for (int i = 0; i <= 4000000; i++) {
            f = f + g;
            g = f - g;
            if (f % 2 == 0) {
                n += f;
            }
        }
        System.out.println("Answer: " + n);
    }
}

The questions is:

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.

like image 766
Spencer H Avatar asked Jan 19 '12 21:01

Spencer H


2 Answers

You are considering the first 4,000,000 terms of the Fibonacci sequence instead of the first x terms which do not exceed 4,000,000.

like image 59
Jeffrey Avatar answered Sep 28 '22 08:09

Jeffrey


Your problem is an integer overflow: in Java, an int variable is limited to Integer.MAX_VALUE (2147483647). If you exceed this value in a computation, you overflow to Integer.MIN_VALUE, the smallest negative value. See:

public class IntegerOverflow {
    public static void main(String[] args) {
        int i = Integer.MAX_VALUE;
        System.out.println("i = Integer.MAX_VALUE: " + i);
        System.out.println("i + 1: " + (i + 1));
        System.out.println("i + 2: " + (i + 2));
    }
}

To avoid overflow problems, perform your computation with arbitrary-precision integers, provided by the java.math.BigInteger class:

import java.math.BigInteger;

public class BigIntegerExample {
    public static void main(String[] args) {
        BigInteger b = BigInteger.valueOf(Long.MAX_VALUE);
        System.out.println("b = Long.MAX_VALUE: " + b);
        System.out.println("b**2: " + b.multiply(b));
        System.out.println("b**3: " + b.pow(3));
        System.out.println("b**10: " + b.pow(10));
    }
}

Note: As you did not ask for help with the problem itself, I am just answering the question. Hope this helps

like image 44
Danilo Piazzalunga Avatar answered Sep 28 '22 09:09

Danilo Piazzalunga