Implement integer exponentiation faster than repeated multiplication The task:


  Implement integer exponentiation. That is, implement the pow(x, y)
  function, where x and y are integers and returns x^y.
  
  Do this faster than the naive method of repeated multiplication.
  
  For example, pow(2, 10) should return 1024.


Solution 1

function pow(x, y) {
  if (!y) { return 1; }
  let tmp = res = x;
  for (let i = 1; i &lt; y; i++) {
    for (let j = 1; j &lt; x; j++) {
      tmp += res;
    }
    res = tmp;
  }
  return res;
}

console.log(pow(2, 10));


I can't claim the following solution to be originally by me. I read it up and implemented it the way I understood. I'm also not sure whether Solution 1 nor Solution 2 is "faster than (...) repeated multiplication".

Solution 2 Also known as "Exponentiation by squaring"

function pow2(x, y) {
  if (!y) { return 1; }
  if (y % 2) {
    return x * pow2(x, y - 1);
  }
  const p = pow2(x, y/2);
  return p * p;
}

console.log(pow2(2,10));
The solution 1 is still a repeated multiplication. The only difference is that the multiplication is implemented as a repeated addition:

    for (let j = 1; j &lt; x; j++) {
        tmp += res;
    }


is a very long way to say

    tmp = res * x;


and obviously it doesn't make the code any faster.



The second solution is almost correct. It fails for negative y (negative is still integer!), and the handling of pow2(0, 0) is questionable.

Besides that, try to avoid the recursion; recursive calls are expensive, and the goal of the exercise is to achieve the maximal speed. There does exist a true honest-to-goodness iterative algorithm.