# Implement integer exponentiation faster than repeated multiplication

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 < y; i++) {
for (let j = 1; j < 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));


This function is very dependent on the inputs, with the function pow being the fastest when the power (second arg) is small, but quickly becomes slower as the power grows.

## Bit-wise and wiser recursing

You can get a tiny bit more out of the pow2 function if you use bit-wise math. The big gain is in avoiding the need to step into the last recursion that returns 1. See (Example B)

The following functions where bench marked. See bottom table.

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

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


## Example B

// Using bitwise math and skipping last recursion when possible
function pow2B(x, y) {
if (y < 2) { return y ? x : 1 }
if (y & 1) { return x * pow2B(x, y & 0x7FFFFFFE)}
const p = pow2B(x, y >> 1);
return p * p;
}


The benchmark results

Time per 10,000 calls in µs (1/1,000,000th sec)
===============================================
args >>   (21, 11) |  (2, 8)  |  (1, 2)
===================|==========|================
pow        0.075µs | 0.014µs  | 0.007µs
pow2       0.014µs | 0.010µs  | 0.005µs (*1)
pow2B (*2) 0.011µs | 0.007µs  | 0.005µs


NOTES

• (*1) The times are right on the precision limits but the pow2 function for (1,2) consistently completed 200 Million operations per second compared to the next best at 194 million. The difference to small to show up in the times.

• (*2) The bit-wise math contributed ~25% of the improvement while the 1 less recursion contributed ~75% of the improvement.

• How did you get the benchmark results ? Ảena the results dependent on the browser engine? Apr 13, 2019 at 6:12
• @thadeuszlay Yes dependent on browser and platform, but you will find that relative performance generally keeps the same order across browsers and platforms. Browser Chrome, Win 10, Laptop i7 1.6Ghz. I use my own benchmarker Apr 13, 2019 at 6:24
• BTW: isn’t the use of bitwise operator a good practice? (It makes it less declarative and more difficult to understand by other programmers.) Apr 13, 2019 at 9:08
• @thadeuszlay It is no more or less declarative than using a + operator. All programmers should know how bitwise operators work and how to use them. If not then they should not be messing with your code. Apr 13, 2019 at 10: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 < 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.

To see for yourself how efficient these algorithms are, you can simply add some counters in the code paths:

let assignments = 0;
let multiplications = 0;

const add = (a, b) => {
return a + b;
};


And in your algorithms, just increment these counters in the correct places.

To check whether the exponentiation is efficient, pow(3, 10) should use less than 10 multiplications.

pow(3, 10)
= pow(3, 5) ** 2
= (pow(3, 4) * 3) ** 2
= ((pow(3, 2) ** 2) * 3) ** 2
= (((pow(3, 1) ** 2) ** 2) * 3) ** 2
= (((3 ** 2) ** 2) * 3) ** 2


That's 4 multiplications instead of 10.

In this example I intentionally use 3 as the base in order to avoid confusion between the 2 from the base and the 2 from the squaring.