Forever Functional: Powers, through the Power of Recursion!
Published: 2023-04-28 23:39:49

by [Federico Kereki](https://blog.openreplay.com/authors/federico-kereki)

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




How can you calculate powers? In JavaScript, that's easy: if you want to calculate 2<sup>3</sup>, 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](https://en.wikipedia.org/wiki/Exponentiation#Identities_and_properties): if p=q+r, then *b*<sup>p</sup>=*b*<sup>q</sup> times *b*<sup>r</sup>. (For example, 2<sup>5</sup> = 2<sup>2</sup> times 2<sup>3</sup>; 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*<sup>0</sup>=1 and *b*<sup>1</sup>=*b*. (OK, I'm skipping a detail; if *b* is zero, *b*<sup>0</sup> [is not defined](https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero); it's an error.) 

Oh, but does this work for [negative powers](https://simple.wikipedia.org/wiki/Exponent#Negative_exponents)? Here's a second math fact: we can write b<sup>p</sup> = (1/b)<sup>-p</sup>, 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<sup>3</sup>= 2 times 2 times 2 = 8. But how do you calculate fractional powers, like 2<sup>6.789</sup>? 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<sup>7</sup>, we can observe that 7=1+6, so the problem is reduced to calculating 2<sup>1</sup> (which is just 2; a base case) times 2<sup>6</sup> (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:

```typescript
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<sup>12</sup>. Sure, you could apply the algorithm in the previous section, but there's a quicker way. We can certainly write 2<sup>12</sup>=2<sup>6</sup> times 2<sup>6</sup>, but you don't need to calculate 2<sup>6</sup> 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<sup>13</sup>? We apply the same idea as in the previous algorithm and write 2<sup>13</sup> = 2<sup>1</sup> times 2<sup>12</sup>, and we then optimize 2<sup>12</sup>. The full calculations for 2<sup>13</sup> would be as follows:

* 13 is odd, so we write 2<sup>13</sup> = 2 times 2<sup>12</sup>
* 12 is even, so 2<sup>12</sup> = (2<sup>6</sup>) squared
* 6 is even, so 2<sup>6</sup> = (2<sup>3</sup>) squared
* 3 is odd, so 2<sup>3</sup> = 2 times 2<sup>2</sup>
* 2 is even, so (trivially!) 2<sup>2</sup> = (2<sup>1</sup>) squared
* 2<sup>1</sup> 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:

```typescript
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<sup>12</sup> = (2<sup>6</sup>) squared, but we can also say that 2<sup>12</sup> = (2 squared)<sup>6</sup>. (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.

```typescript
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<sup>15</sup> requires 6 multiplications, but can you find a way to do this with fewer operations?*

---

<div style="background-color:#efefef; border-radius:8px; padding:10px; display:block;">
<hr/>
<h3><em>Session Replay for Developers</em></h3> 
<p><em>Uncover frustrations, understand bugs and fix slowdowns like never before with <strong><a href="https://github.com/openreplay/openreplay" target="_blank">OpenReplay</a></strong> — an open-source session replay suite for developers. It can be <strong>self-hosted</strong> in minutes, giving you complete control over your customer data.</em></p>
<img alt="OpenReplay" style="margin-top:5px; margin-bottom:5px;" width="768" height="400" src="https://raw.githubusercontent.com/openreplay/openreplay/main/static/openreplay-git-hero.svg" class="astro-UXNKDZ4E" loading="lazy" decoding="async">
<p><em>Happy debugging! <a href="https://openreplay.com" target="_blank">Try using OpenReplay today.</a></em><p>
<hr/>
</div>

## Fractional powers

How can we calculate 2<sup>5.789</sup>? That's a tough one! We can split off the integer part of the exponent and write 2<sup>5</sup> times 2<sup>0.789</sup>. 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*<sup>1</sup> = *b*<sup>0.5</sup> squared, and from that, it follows that *b*<sup>0.5</sup> = &radic;*b*. And why is this good? There exists [a very old iterative algorithm](https://www.cantorsparadise.com/a-modern-look-at-square-roots-in-the-babylonian-way-ccd48a5e8716) 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](https://xlinux.nist.gov/dads/HTML/squareRoot.html) 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<sup>0.789</sup>. We can write 0.789 = 0.5 + 0.289, and then we need to calculate 2<sup>0.5</sup> (a square root! We know how to do that!) times 2<sup>0.289</sup>... a new problem!

However, if we take square roots again and again, we find:
* 2<sup>0.25</sup> is the square root of the square root of 2, its fourth root. 
* 2<sup>0.125</sup> is the square root of the fourth root of 2, its eighth root.
* 2<sup>0.0625</sup> 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<sup>0.789</sup> is smaller than 2<sup>1</sup>, so we skip 1
* 2<sup>0.789</sup> = 2<sup>0.5</sup> (known) times 2<sup>0.289</sup>
* 2<sup>0.289</sup> = 2<sup>0.25</sup> (known) times 2<sup>0.039</sup>
* 2<sup>0.039</sup> is smaller than 2<sup>0.125</sup>, so we skip 0.125
* 2<sup>0.039</sup> is smaller than 2<sup>0.0625</sup>, so we also skip 0.0625
* 2<sup>0.039</sup> = 2<sup>0.03125</sup> (known) times 2<sup>0.00775</sup>
* 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!)

```typescript
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:

```javascript
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<sup>0.789</sup> by first finding 2<sup>101</sup> and then taking square roots 7 times (because 128 = 2<sup>7</sup>). What problem could [this approach](https://en.wikipedia.org/wiki/Exponentiation#Rational_exponents) have?*

---

## Conclusion: Putting everything together

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

```typescript
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

1. The algorithm would work, but it would do an extra multiplication: calculating *b*<sup>1</sup> would be done as *b* times *b*<sup>0</sup> instead of directly returning *b*.
2. You can do better by starting with 2, then 2<sup>2</sup>, 2<sup>3</sup>, 2<sup>6</sup>, 2<sup>12</sup>, and finally 2<sup>15</sup>. Each value in the sequence can be calculated by squaring or multiplying previously calculated numbers, and we just needed 5 operations in all.
3. 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.
4. 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<sup>101</sup> comes out to 1.72795... instead of the correct value 1.72788... so we get a precision of about 3 decimals.