CODEWITHSUNDEEP
javadoublelong-integer
Ladybro
Ladybro

Reputation: 806

Loss of precision multiplying large longs

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?

Upvotes: 2

Views: 544

Answers (2)

ddmps
ddmps

Reputation: 4380

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.

Upvotes: 1

phibao37
phibao37

Reputation: 2350

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;
        }
    }

}

Upvotes: 1

Related Questions