5

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);

ted
  • 5,219
  • 7
  • 36
  • 63

3 Answers3

12

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.

Draco Ater
  • 20,820
  • 8
  • 62
  • 86
  • This fails when the modulus is large. – Doug Sep 16 '17 at 22:22
  • @Doug, oddly, you and I both happened to view this question that is over 6 years old within 1 hour of each other. Regardless, out of curiosity how large are you referring to? Of course, it should be expected that the function will fail on an integer value *n* where `n >= 2^53`, but that is a limitation of the language's standards, not a limitation of this answer itself. So, just to clarify, are you saying this answer will fail for `n >= 2^53` or are you saying it will fail even when the modulus is less than `2^53`? – Spencer D Sep 17 '17 at 00:13
  • I was trying to solve a hackerrank challenge that required use of modulo 10^9+7. When squaring ints, this mod exceeds `Math.floor(Math.sqrt(Number.MAX_SAFE_INTEGER))` and the failure happens silently. Hackrrank provides `bignumber.js` but using this lib is kind of a bummer when trying to stay vanilla. – Doug Sep 25 '17 at 18:41
2

Your method is good so far, but you will want to do http://en.wikipedia.org/wiki/Exponentiation_by_squaring also known as http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

The idea is that x^45 is the same as (expanded into binary) x^(32+8+4+1), which is the same as x^32 * x^8 * x^4 * x^1

And you first calculate x^1, then x^2 == (x^1)^2, then x^4 == (x^2)^2, then x^8 == (x^4)^2, then...

ninjagecko
  • 88,546
  • 24
  • 137
  • 145
1

you can also use the mountgomery reduction in combination with exponentiation which is largely useful for large exponents > 256:

http://en.wikipedia.org/wiki/Montgomery_reduction#Modular_exponentiation

It has also been implemented in this BigInteger Library for RSA-encryption:

http://www-cs-students.stanford.edu/~tjw/jsbn/

Martin Baum
  • 49
  • 2