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

Popular posts from this blog

javascript - Bootstrap Popover: iOS Safari strange behaviour -

Magento/PHP - Get phones on all members in a customer group -

session - Logging Out Using PHP -