CODEWITHSUNDEEP
javascriptnode.jsprecision
Adam
Adam

Reputation: 12660

Precision and Large Numbers

I've written a function in JavaScript to calculate prime numbers:

function isDivisible(dividend, divisor) {
    return dividend % divisor === 0;
}

function isPrime(n) {
    var factor = 2;

    n = Math.abs(n);

    if (n <= 1) {
        return true;
    }

    while (factor < n) {
        if (isDivisible(n, factor)) {
            return false;
        }

        factor += 1;
    }

    return true;
}
function getPrimes(max) {
    var primes = [], i = 1;

    while (i <= max) {
        if (isPrime(i)) {
            primes.push(i);
        }

        i += 1;
    }

    return primes;
}

function M(p) {
    return Math.pow(2, p) - 1;
}

function isMersennePrime(p) {
    var s, m, i;

    s = 4;
    m = M(p);

    for (i = 0; i < p - 2; i++) {
        s = (s * s - 2) % m;
    }

    return s === 0 ? true : false;
}

function findLargestMersennePrime(pMax) {
    var p, primes = getPrimes(pMax);

    while (primes.length) {
        p = primes.pop();

        if (isMersennePrime(p)) {
            return M(p);
        }
    }

    return null;
}

The function, findLargestMersennePrime, takes argument, p, which is used as a seed value for calculating Mersenne Prime numbers, M(p). The program uses the Lucas Lehmer Primality test.

The test cases I'm using correspond to this table. For any given input, pMax, the program gets a list of prime numbers less than or equal to pMax, and then checks to see if the Mersenne number of p is prime. The test cases pass for the first 7 Mersenne Primes, that is p < 31.

When p = 31, 61, 89... the M(p) is prime, but the function isMersennePrime(31) always returns false.

I think this may have something to do with the maximum size of number in JavaScript. I'm running Node 0.5. Is it a bug in my code or a limitation of JavaScript? Is there another language that would be better suited for this problem or a way of making it work in JS?

Upvotes: 2

Views: 841

Answers (2)

Matthew Crumley
Matthew Crumley

Reputation: 102725

A language with built-in large integers (like Python, Ruby, Scheme to name a few) would make it easier, but there are several big integer libraries for JavaScript that would also work.

One disadvantage is that you can't use the normal JavaScript operators anymore. It will also be slower than a language with native big integers.

Here are a couple examples:

Upvotes: 3

hugomg
hugomg

Reputation: 69944

Javascript numbers are standard double precision floating numbers and are good up to 252 - 1. This should be enough for your 8th Mersenne prime (but will not be precise enough for the 9th)

Upvotes: 4

Related Questions