ted ted -4 years ago 157
Javascript Question

Pow and mod function optimization

I need to create an optimized function to count Math.pow(a,b) % c; in Javascript;

There's no problems while counting small numbers like:

Math.pow(2345,123) % 1234567;


But if you try to count:
Math.pow(2345678910, 123456789) % 1234567;

you'll get incorrect result because of Math.pow() function result that cannot count up "big" numbers;

My solution was:

function powMod(base, pow, mod){
var i, result = 1;
for ( i = 0; i < pow; i++){
result *= base;
result %= mod;
}
return result;


Though it needs a lot of time to be counted;

Is it possible to optimized it somehow or find more rational way to count up Math.pow(a, b) % c; for "big" numbers? (I wrote "big" because they are not really bigIntegers);

Answer Source

Based on SICP.

function expmod( base, exp, mod ){
  if (exp == 0) return 1;
  if (exp % 2 == 0){
    return Math.pow( expmod( base, (exp / 2), mod), 2) % mod;
  }
  else {
    return (base * expmod( base, (exp - 1), mod)) % mod;
  }
}

This one should be quicker than first powering and then taking remainder, as it takes remainder every time you multiply, thus making actual numbers stay relatively small.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download