Javascript 自制 pow 与模数

Question

我得到了这段用 JavaScript 编写的代码，但是对于大输入它返回了错误的数字。
它应该用模(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的答案用于实现一些简单的算法 a*a mod n without overflow .我已经改编了 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);

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