OpenReplay Tech Blog

Posted on Apr 28, 2023 • Originally published at blog.openreplay.com

Forever Functional: Powers, through the Power of Recursion!

Recursion is a powerful tool for algorithm design, and this article will show several examples of its application to produce some math calculations.

How can you calculate powers? In JavaScript, that's easy: if you want to calculate 2³, you can either write Math.pow(2,3) or (in a more modern way) 2**3. But here's the question: how would you code a power-calculation function of your own? Obviously, there's no actual need for that -as I wrote, JavaScript already has that- but working out the code ourselves will be an interesting exercise in recursion and algorithm design, so let's get to work! (And, to whet your curiosity, we'll also throw in some questions for you to puzzle over!) We will restrict ourselves to basic arithmetic (addition, subtraction, multiplication, and division) but that won't be an obstacle for our code!

Just two math facts

I promise we'll use little math. We will basically work with the following identity: if p=q+r, then b^p=b^q times b^r. (For example, 2⁵ = 2² times 2³; 32 = 4 times 8.) This already provides us with ideas for recursion; we can calculate the p-th power if we know how to calculate two lower powers, the q-th, and the r-th; good! For recursion we need at least one base case, and we can have two since for all b, b⁰=1 and b¹=b. (OK, I'm skipping a detail; if b is zero, b⁰ is not defined; it's an error.)

Oh, but does this work for negative powers? Here's a second math fact: we can write b^p = (1/b)^-p, so instead of raising a number to a negative power, we raise the inverse of the number to a positive power: good! (Again, I'm skipping a detail; b cannot be zero here either; that would be an error too.)

We now have the basics for an algorithm -- and I'm skipping the error checks because they are not hard to add, and we can then focus on the main parts of the code:

To calculate b to the p power:
   if p is negative, return (1/b) to the -p power (unless b is zero: an error)
   if p is zero, return 1 (again, unless b is zero, which would be an error)
   if p is one, return b
   otherwise, split p = q + r
   calculate x = b to the q power
   calculate y = b to the r power
   return x times y

There's only one small detail... how do we split p in q+r? We should do this in some way that makes calculations easy. We have two problems: for integer powers, a simple loop gets you that 2³= 2 times 2 times 2 = 8. But how do you calculate fractional powers, like 2^6.789? Let's first deal with integer powers and later see how to deal with fractional ones.

For simplicity, in the rest of the algorithm we will calculate only positive powers, and we won't include any checks to not obscure the main logic.

Integer powers

As described above, let's first work out how to calculate integer powers. We'll first see a basic loop-style solution, which you'd do by hand, and then optimize it with a much quicker algorithm.

A loop-style solution

How can we calculate integer powers? The first solution we can work on is equivalent to a loop. To calculate 2⁷, we can observe that 7=1+6, so the problem is reduced to calculating 2¹ (which is just 2; a base case) times 2⁶ (which is a simpler case that we will solve with recursion). The following algorithm will do this:

To calculate b to the p power:
   if p is zero, return 1
   if p is one, return b
   otherwise, split p = 1 + (p-1)
   calculate x = b to the (p-1) power
   return x times b

We can code it quickly:

function intPower(b: number, p: number): number {
  if (p === 0) {
    return 1;
  } else if (p === 1) {
    return b;
  } else {
    return b * intPower(b, p - 1);
  }
}

console.log(intPower(2,7)); 
// 128

That works! But can we not do any better in terms of the number of multiplications? Yes, we can; let's see how.

QUESTION #1: Would the algorithm also work if we removed the if that considers the case when p===1? Would it still produce the same result?

The "square and multiply" way

Suppose you want to calculate 2¹². Sure, you could apply the algorithm in the previous section, but there's a quicker way. We can certainly write 2¹²=2⁶ times 2⁶, but you don't need to calculate 2⁶ twice; calculate it just once, and then square the result! For even powers, this avoids lots of multiplications, so it's good.

OK, but what about odd powers, say for 2¹³? We apply the same idea as in the previous algorithm and write 2¹³ = 2¹ times 2¹², and we then optimize 2¹². The full calculations for 2¹³ would be as follows:

13 is odd, so we write 2¹³ = 2 times 2¹²
12 is even, so 2¹² = (2⁶) squared
6 is even, so 2⁶ = (2³) squared
3 is odd, so 2³ = 2 times 2²
2 is even, so (trivially!) 2² = (2¹) squared
2¹ is just 2

This algorithm needed just 5 multiplications (each squaring needs one) instead of the 12 ones the previous algorithm would have needed. The algorithm is now:

To calculate b to the p power:
   if p is zero, return 1
   if p is one, return b
   if p is odd, return b times b to the (p-1) power
   else (when p is even) 
     calculate z = b to the (p/2) power
     return z squared

We can implement this directly:

function intPower(b: number, p: number): number {
  if (p === 0) {
    return 1;
  } else if (p === 1) {
    return b;
  } else if (p % 2 === 1) {
    return b * intPower(b, p - 1);
  } else /* p % 2 === 0 */ {
    const z = intPower(b, p / 2);
    return z * z;
  }
}

Excellent, by using recursion we managed to reduce the number of operations! Agreed, that's not really too important if you are dealing with small powers, but in certain cryptographic algorithms, we need to calculate really large powers, and without this speedy version, we wouldn't be able to do it at all.

QUESTION #2: What would happen if we had written return intPower(b,p/2) * intPower(b,p/2) for even values of p?

A slightly different way

Let's look at the previous method. We wrote that 2¹² = (2⁶) squared, but we can also say that 2¹² = (2 squared)⁶. (Check it out!) The corresponding algorithm is very similar; only the last line changes:

To calculate b to the p power:
   if p is zero, return 1
   if p is one, return b
   if p is odd, return b times b to the (p-1) power
   else (when p is even) return (b squared) to the (p/2) power

The only difference is that the implementation is one line shorter.

function intPower(b: number, p: number): number {
  if (p === 0) {
    return 1;
  } else if (p === 1) {
    return b;
  } else if (p % 2 === 1) {
    return b * intPower(b, p - 1);
  } else /* p % 2 === 0 */ {
    return intPower(b * b, p / 2);
  }
}

The total number of multiplications is precisely the same; we just work in a slightly different way. OK, we're about done with integer powers; what happens if we want to calculate fractional powers? That's a whole different thing!

QUESTION #3: This algorithm is good but not always optimum. Calculating 2¹⁵ requires 6 multiplications, but can you find a way to do this with fewer operations?

Session Replay for Developers

Uncover frustrations, understand bugs and fix slowdowns like never before with OpenReplay — an open-source session replay suite for developers. It can be self-hosted in minutes, giving you complete control over your customer data.

Happy debugging! Try using OpenReplay today.

Fractional powers

How can we calculate 2^5.789? That's a tough one! We can split off the integer part of the exponent and write 2⁵ times 2^0.789. We can easily find the first result, but how do we deal with the second one?

We need an extra trick. Applying the same results we used earlier, we can write b¹ = b^0.5 squared, and from that, it follows that b^0.5 = √b. And why is this good? There exists a very old iterative algorithm that lets you find square roots only using basic arithmetic operations, so we can use it for our needs.

(To calculate square roots by hand, there's an algorithm that you can use that also makes do with simple arithmetic. I was taught this algorithm in high school, though I admit I never used it!)

So, let's return to 2^0.789. We can write 0.789 = 0.5 + 0.289, and then we need to calculate 2^0.5 (a square root! We know how to do that!) times 2^0.289... a new problem!

However, if we take square roots again and again, we find:

2^0.25 is the square root of the square root of 2, its fourth root.
2^0.125 is the square root of the fourth root of 2, its eighth root.
2^0.0625 is the square root of the eighth root of 2, its sixteenth root.
and so on -- we can find the 0.03125, 0.015625, 0.0078125, etc. powers by repeatedly taking square roots.

There's a whole slew of fractional powers (0.5, 0.25, 0.125, 0.0625, 0.03125, 0.015625, 0.0078125, etc.) that we can calculate by just taking square roots, and we can now write:

2^0.789 is smaller than 2¹, so we skip 1
2^0.789 = 2^0.5 (known) times 2^0.289
2^0.289 = 2^0.25 (known) times 2^0.039
2^0.039 is smaller than 2^0.125, so we skip 0.125
2^0.039 is smaller than 2^0.0625, so we also skip 0.0625
2^0.039 = 2^0.03125 (known) times 2^0.00775
etc.

We need to keep track of the successive exponents we try out (1, 0.5, 0.25, etc.) and the corresponding sequence of square roots that we multiply to calculate the final result. There's only one problem; the comparisons may never end! We'll have to stop doing calculations when the last term we have to multiply by is very close to 1; we cannot keep doing recursion forever! For integer powers, we know the calculation will end, but for fractional powers, the procedure may go on indefinitely.

(Why compare with 1? If you take any number, large or small, and you keep taking square roots, it will always converge to 1; try it out with a calculator!)

function fracPower(b: number, p: number, e = 1): number {
  if (Math.abs(b - 1) < 0.000_000_000_000_001) {
    return 1;
  } else {
    e /= 2;
    b = Math.sqrt(b);

    if (p > e) {
      return b * fracPower(b, p - e, e);
    } else {
      return fracPower(b, p, e);
    }
  }
}

In this algorithm, we want to calculate b to the p power, and p is between 0 and 1; e will be 1, 0.5, 0.25, 0.125, etc. We used Math.sqrt(...) just for brevity; to really fulfill the conditions we set up at the beginning of the article (using only the four basic arithmetic operations) we should have calculated the square root "by hand"; sorry about that!

We can check that our code works:

console.log(fracPower(2, 0.5), 2 ** 0.5);
// 1.414213562373092 1.4142135623730951

console.log(fracPower(2, 0.123456789), 2 ** 0.123456789);
// 1.0893418703486817 1.0893418703486832

console.log(fracPower(3, 0.987654321), 3 ** 0.987654321);
// 2.9595853498312765 2.959585349831282

There are minor rounding errors, but we won't try to fix that; it's beyond the scope of the article.

QUESTION #4: Somebody observed that 0.789 is close to 101 / 128, so you could approximate 2^0.789 by first finding 2¹⁰¹ and then taking square roots 7 times (because 128 = 2⁷). What problem could this approach have?

Conclusion: Putting everything together

We now know how to do both integer and fractional powers; we can combine everything.

function fullPower(b: number, p: number): number {
  if (p < 0) {
    return fullPower(1 / b, -p);
  } else {
    const intExp = Math.trunc(p);
    const fracExp = p - intExp;
    return intPower(b, intExp) * fracPower(b, fracExp);
  }
}

This is practically complete, but it's as far as we'll get. We aren't checking for possible errors (try calculating fullPower(0,-3) to see the code fail) and there are more cases that won't work and we didn't consider, such as taking the square root of a negative number as in fullPower(-3.1, 0.5).

Don't worry about errors much! Our objective wasn't to redo what JavaScript provides but to study how to develop the needed algorithms. And, as we proposed, we did all the calculations using recursion and plain arithmetic - an unexpected result!

Answers to questions

The algorithm would work, but it would do an extra multiplication: calculating b¹ would be done as b times b⁰ instead of directly returning b.
You can do better by starting with 2, then 2², 2³, 2⁶, 2¹², and finally 2¹⁵. Each value in the sequence can be calculated by squaring or multiplying previously calculated numbers, and we just needed 5 operations in all.
If you calculate intPower(b,p/2) twice, you lose all your advantage and savings in operations and end up doing the same number of multiplications as our first algorithm did.
Raising a number to the 101st power would cause an overflow for most numbers - and if not, it's also likely that the limited precision of computer numbers would produce a bad final result. With my scientific calculator, the 128th root of 2¹⁰¹ comes out to 1.72795... instead of the correct value 1.72788... so we get a precision of about 3 decimals.