ted -4 years ago 157

Javascript Question

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**

Latest added