Getting negative/wrong values although using identifier "long"

Question

I am trying to calculate the sum of the first, even four million Fibonacci-numbers. However, after a while, only the Y-values are being printed out as the values get larger, even though I'm using the identifier long.

These are the start values:

long amount = 4000000;
long x = 1;
long y = 2;
long sum = 2;

Here is a for-loop that sums up and prints out the numbers as the program runs.

for (int i = 0; i < amount - 1; i++) {
    if (x > y) {
        y = x + y;
        if (y % 2 == 0) {
            sum += y;
        }           
        System.out.println("X: " + x);
    } else {
        x = x + y;
        if (x % 2 == 0) {
            sum += x;
        }   
        System.out.println("Y: " + y);
    }
}
System.out.println("Summa: " + sum);

First Fibonacci numbers output correctly:

Y: 2
X: 3
Y: 5
X: 8
Y: 13
X: 21
Y: 34
X: 55
Y: 89
X: 144
Y: 233
X: 377

Output after a while:

X: 8838822096666553613
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303
Y: 9212367363430683303

Why is only Y getting calculated after a while? Is my code wrong?

`X` overflows and becomes negative, so `(x > y)` is always false — Augusto, Feb 22 '16 at 08:45
long max value is 2^63 so you're at the limit. Use BigInteger — Toumash, Feb 22 '16 at 08:46
@Mourad Kourie you dont need to try it. I took 3 secounds to calculate the first 10000 with your algorithem, so you wont be able to calculate the first four million with it. — kai, Feb 22 '16 at 08:54

score 6 · Accepted Answer · answered Feb 22 '16 at 08:47

6

The number you're calculating is quite big... too big for a Long. Since you're doing integer calculations, replace the long for a BigInteger. Since BigInteger is an object, you won't be able to use the + or % operators, and you'll need to use the method calls add() and mod().

answered Feb 22 '16 at 08:47

Augusto

28,839
5
58
88

Thanks! I'll try it out. – Mourad Kourie Feb 22 '16 at 08:49

Manos Nikolaidis · Answer 2 · 2016-02-22T08:58:26.673

2

The maximum value a long can take is 9223372036854775807 (Long.MAX_VALUE). If the result of an addition exceeds that, it will overflow and return a negative value :

long x = 8838822096666553613L;
long y = 9212367363430683303L;
y = x + y;

will result in a y value of -395554613612314700. Therefore this comparison will fail :

if (x > y) {

and this is why you only see Y values getting printed

edited Feb 22 '16 at 08:58

answered Feb 22 '16 at 08:50

Manos Nikolaidis

21,608
12
74
82

Getting negative/wrong values although using identifier "long"

2 Answers2