Loss of precision multiplying large longs

Question

I'm working on a problem statement that essentially is a fibonacci sequence:

Given two initial values as inputs, you calculate term x = (term x-1)^2 + (term x-2)

So, given input 0 1 5, we want to calculate term 5 of the sequence, which is done in the following way:

Term 3 = (Term 2)^2+(term 1) = 1^2 + 0 = 1

Term 4 = (Term 3)^3+(term 2) = 1^1 + 1 = 2

Term 5 = 2^2+1 = 5

And so on.

My problem comes when I try to calculate a large value, say the 10th. Using longas my data type, I lose precision precisely at the 10th value. The expected/correct value is `84266613096281243382112, but I get..

0 1 10
Term number 3 has value 1
Term number 4 has value 2
Term number 5 has value 5
Term number 6 has value 27
Term number 7 has value 734
Term number 8 has value 538783
Term number 9 has value 290287121823
Term number 10 has value 1886167576011600224

Doing the same problem using doubleas my data type instead gives me the correct answer, but not in the format I need (this is for an automated test case).

0 1 10
Term number 3 has value 1.0
Term number 4 has value 2.0
Term number 5 has value 5.0
Term number 6 has value 27.0
Term number 7 has value 734.0
Term number 8 has value 538783.0
Term number 9 has value 2.90287121823E11
Term number 10 has value 8.426661309628124E22

Why am I experiencing this loss of precision with long and how can I prevent it/get my desired output?

possible duplicate of [java Long primitive type maxumum limit](http://stackoverflow.com/questions/15505515/java-long-primitive-type-maxumum-limit) — jww, Oct 04 '14 at 03:18

ddmps · Answer 1 · 2014-10-04T03:20:12.127

1

That is because a long's max value is 2^63-1 (or 9.223372e+18). You simply cannot go higher than that.

If double is of enough precision for your application, you can look at formatting it as per specification with for instance DecimalFormat.

If double is not of sufficient precision you can look at using BigInteger. But it will come at a much higher performance cost.

edited Oct 04 '14 at 03:20

answered Oct 04 '14 at 03:10

ddmps

4,350
1
19
34

score 1 · Answer 2 · answered Oct 04 '14 at 03:19

Try with BigInteger class, it work:

import java.math.BigInteger;

public class Test {

    public static void main(String[] args) {
        BigInteger x1, x2, x3;

        x1 = new BigInteger("0");
        x2 = new BigInteger("1");

        for (int i = 3; i <= 10; i++){
            x3 = x2.multiply(x2).add(x1);
            System.out.println(i + ":" + x3);
            x1 = x2;
            x2 = x3;
        }
    }

}

Loss of precision multiplying large longs

2 Answers2