Javascript self made pow with modulo

Question

I got this code written in JavaScript, but it returns wrong number for large input.
It should calculate the base to the exponent(ex) power with modulo(mo).
I wrote equivalent code in C and is working. Please can someone tell me what is wrong.
Try to test Fermat's theorem for modulo 10^9 +7.

function powFun(base, ex, mo) {
    var r;
    if(ex === 0) 
        return 1;
    else if(ex % 2 === 0) {
        r = powFun(base, ex/2, mo) % mo ;
        return (r * r) % mo;
    }else 
        return (base * powFun(base, ex - 1, mo)) % mo;
}

please add some test data. on what input it fails and what is the expected output? — Luboš Turek, Jun 03 '15 at 21:03
How big are the numbers? See http://stackoverflow.com/questions/307179/what-is-javascripts-highest-integer-value-that-a-number-can-go-to-without-losin for the maximum integer that can be represented accurately in JS. — Barmar, Jun 03 '15 at 21:05
the input values are, base = 4, ex = 1000000006, mo = 1000000007. — Sim, Jun 03 '15 at 21:24
i solved problem in C i am just curious why is it not working in javascript. — Sim, Jun 03 '15 at 21:26
Read the page linked to by @Barmar — Javascript can only handle integers up to 53 bits in size. To calculate modular products correctly, the largest modulus you can work with is 2^(53/2) = 94906265. This is a lot smaller than 10^9 + 7. So you either have to find a Javascript library that supports large integers, or write your own routines. — r3mainer, Jun 03 '15 at 22:13
@squeamishossifrage: wouldn't that be (2^53)/2 ? (or 2^(53-1)) — slebetman, Jun 04 '15 at 01:53
@slebetman It would if the algorithm worked by adding numbers together. You can calculate `(r+r)%m` without overflow if `r` is a 52-bit number, but to calculate `(r*r)%m`, you'll get an overflow before taking the modulus if `r` is a 27-bit number — r3mainer, Jun 04 '15 at 07:55
@squeamishossifrage: Ah OK. I get it. I forgot that the result of a binary multiply operation is double the number of bits of the inputs. — slebetman, Jun 04 '15 at 07:58
@Sim: The `53/2` is because multiply operations in binary results in double the number of bits of the inputs. So the only "safe" inputs are those that are `53/2` bits. — slebetman, Jun 04 '15 at 08:00

score 1 · Accepted Answer · edited May 23 '17 at 11:51

The overflow is occurring in this line:

return (r * r) % mo;

Refer to the answers to this question for some simple algorithms to implement a*a mod n without overflow. I've adapted one of the answers to Javascript below:

function addmod(x, y, n)
{
    // Precondition: x<n, y<n
    // If it will overflow, use alternative calculation
    if (x + y <= x) x = x - (n - y) % n;
    else x = (x + y) % n;
    return x;
}

function sqrmod(a, n)
{
    var b;
    var sum = 0;

    // Make sure original number is less than n
    a = a % n;

    // Use double and add algorithm to calculate a*a mod n
    for (b = a; b != 0; b >>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}

function powFun(base, ex, mo) {
    var r;
    if(ex === 0) 
        return 1;
    else if(ex % 2 === 0) {
        r = powFun(base, ex/2, mo) % mo ;
        // return (r * r) % mo;
        return sqrmod(r, mo);
    }else 
        return (base * powFun(base, ex - 1, mo)) % mo;
}

result = powFun(4, 1000000006, 1000000007);

alert(result);

To support even bigger numbers, use a library that supports large integers.

Good answer, but you should probably change the first line of `addmod()` to `if (x + y <= x) x = (x - (n - y))%n;` — r3mainer, Jun 04 '15 at 08:03

Javascript self made pow with modulo

1 Answers1