Javascript 自制 pow 取模

Question

我用 JavaScript 编写了这段代码，但它 returns 大输入的数字错误。
它应该用模（mo）计算指数（ex）幂的底数。
我用 C 编写了等效代码并且正在运行。请有人告诉我出了什么问题。
尝试测试费马定理的模数 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;
}

Answer 1

这一行发生溢出：

return (r * r) % mo;

参考下面this question for some simple algorithms to implement a*a mod n without overflow. I've adapted one of the answers到Javascript的答案：

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

要支持更大的数字，请使用支持大整数的库。

Javascript 自制 pow 取模

Javascript self made pow with modulo

javascript

algorithm

pow