algorithm - Javascript self made pow with modulo -
i got code written in javascript, returns wrong number large input.
should calculate base exponent(ex) power modulo(mo).
wrote equivalent code in c , working. please can tell me wrong.
try test fermat's theorem 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; }
the overflow occurring in line:
return (r * r) % mo; refer answers this question simple algorithms implement a*a mod n without overflow. i've adapted one of answers javascript below:
function addmod(x, y, n) { // precondition: x<n, y<n // if 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 less n = % n; // use double , add algorithm calculate a*a mod n (b = a; b != 0; b >>= 1) { if (b & 1) { sum = addmod(sum, a, n); } = 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 bigger numbers, use library supports large integers.
Comments
Post a Comment