Dealing with innaccuracy from double arithmetic?

Question

I've written a method that tests whether a number is prime or not. To maximise the range of numbers that the user can input, I wanted to use doubles. The issue is, after testing it on a very large prime, like 40 digits or so, my method returns false (I've already tested the logic with an int version, and it works just fine as far as I can tell). Here is my code:

public static boolean isPrime(double number) {

    double sqrt = Math.sqrt(number);

    for(double i = 2; i<= sqrt; i++) {
        if(number%i == 0) {
            return false;
        }
    }

I know the reason it's not working at very high numbers is because of the accuracy error, but is there around this?

Or better [BigInteger](https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html). — vanje, Dec 21 '17 at 12:56
Why would you check if a double is a prime number? Primes must be integral. The sqrt is only required to set the upper bound of the highest possible factor. — StuartLC, Dec 21 '17 at 12:56
Use long or BigInteger. And never use floating point types when you want to solve integer problems. — GhostCat, Dec 21 '17 at 13:06

Stephen C · Accepted Answer · 2017-12-21T13:31:37.897

I know the reason it's not working at very high numbers is because of the accuracy error, but is there around this?

Yes. Use BigInteger.

Note that long would be better than double, since long can represent all integers up to 2^63 - 1 precisely. By contrast, with double you start losing precision at 2^53 + 1. However neither of these types are suitable for 40 (decimal) digit numbers.

BigInteger arithmetic is significantly slower, but the you will be able to go up to (at least) 2^Integer.MAX_VALUE ... provided that you have enough heap space.

Dealing with innaccuracy from double arithmetic?

1 Answers1