preface

There is a library function in JavaScript (math.pow ()) that can raise a number to a power. This article will implement a function similar to pow. Interested developers are welcome to read this article.

Implementation approach

At first glance, some developers might think about this for a few seconds and think it’s easy. Directly iterate over the square number, multiply the base number by the previous calculation result, directly shuttle 🤓, and soon write the code, as shown below:

  /** ** Compute a number to the power *@param The base base number *@param Exponent index * /
  public power(base: number.exponent: number) :number {
    let result = 1;
    for (let i = 1; i <= exponent; i++) {
      result *= base;
    }
    return result;
  }
Copy the code

Careful developers may have noticed that this code only takes into account positive exponents and miscalculates when the input exponent is less than 1 🌝

A comprehensive solution

Next, we take the negative and 0 exponents into account to clarify the implementation idea:

  • When the exponent is negative, you take the absolute value of the exponent, you take the exponent to the power and then you take the inverse
  • When the exponent is zero, we have to consider two cases:
    • When the base is 0 and the index is negative, there will be reciprocal of 0, which will lead to errors in the program operation. Fault tolerance processing is required to inform the caller of the error information
    • When the base is 0 and the exponent is 0, it doesn’t make sense mathematically, so we can return the result either 0 or 1

We translate the above ideas into code as follows:

  /** ** Compute a number to the power *@param The base base number *@param Exponent index * /
  public power(base: number.exponent: number) :number | string {
    // Find the absolute value of the index
    const absExponent = Math.abs(exponent);
    // The program will fail
    if (base === 0 && exponent < 0) {
      return "Parameter error: 0 to the negative power cannot be calculated";
    }

    // It is mathematically meaningless when both the base and the exponent are 0
    if (base === 0 && exponent === 0) {
      return 0;
    }

    let result = 1;
    for (let i = 1; i <= absExponent; i++) {
      result *= base;
    }

    // If the exponent is less than 0, calculate the inverse of the result
    if (exponent < 0) {
      result = 1 / result;
    }
    return result;
  }
Copy the code

Let’s take everything into account, pass in the above code as an argument, and observe the result, as follows:

The optimal solution

So that’s good, but it’s not optimal, so let’s look at a better solution.

The code in the above code that loops to the exponential power of the base can be broken down into a function, as follows:

  /** ** find the base to the exponential *@param base
   * @param exponent* /
  private static powerWithExponent(base: number, exponent: number) {
    let result = 1;
    for (let i = 1; i <= exponent; i++) {
      result *= base;
    }
    return result;
  }
Copy the code

After the split, let’s consider this scenario:

When the exponent is 32, you need to do 31 multiplication in the loop of the above function. However, our goal is to find a number to the 32nd power, and if we already know it to the 16th power, we can just square it once more. And the sixteenth power is the eighth power squared.

Similarly, we only need to do 5 multiplications to get to the 32nd power:

  • First square
  • Take the square to the fourth power
  • Take the fourth power to the eighth power
  • To the 16th power
  • Take the sixteenth power to the thirty-second power

With that in mind, let’s set the required power to n, then:

  • When n is even, we can split itn/2 * n/2
  • When n is odd, it can be split into(n-1)/2 * (n-1)/2

After the results are calculated on both sides of the multiply equation, the above rules can still be applied to the results until n is 0 or 1. The formula can be summarized as follows:

The implementation code

With the formula, it didn’t take long to figure out how to solve this problem recursively. Let’s draw the recursive stack, as shown below:

After thinking clearly, you can happily enter the coding link 🤓, the complete code is as follows:

export default class IntegerPower {
  /** ** Compute a number to the power *@param The base base number *@param Exponent index * /
  public power(base: number.exponent: number) :number | string {
    // Find the absolute value of the index
    const absExponent = Math.abs(exponent);
    // The program will fail
    if (base === 0 && exponent < 0) {
      return "Parameter error: 0 to the negative power cannot be calculated";
    }

    // It is mathematically meaningless when both the base and the exponent are 0
    if (base === 0 && exponent === 0) {
      return 0;
    }

    // Take the power
    let result = this.powerWithExponent(base, absExponent);

    // If the exponent is less than 0, calculate the inverse of the result
    if (exponent < 0) {
      result = 1 / result;
    }
    return result;
  }

  /** ** find the base to the exponential *@param The base base number *@param Exponent index * /
  private powerWithExponent(base: number.exponent: number) :number {
    // Recursive termination condition
    if (exponent === 0) {
      // Non-zero to the 0 power is 1
      return 1;
    }
    if (exponent === 1) {
      // Any number raised to the 0 power is itself
      return base;
    }

    // Recurse to the exponent /2
    // Use the right shift operator instead of dividing by 2
    let result =
      this.powerWithExponent(base, exponent >> 1) *
      this.powerWithExponent(base, exponent >> 1);

    // If the exponent is odd, result is result times base
    if (exponent % 2= = =1) {
      result *= base;
    }
    returnresult; }}Copy the code

In the above code, I used the right shift operator instead of division to speed up the execution of the code. Developers who are not familiar with this should refer to my other article: Numbers in binary – right shift operators

For developers unfamiliar with recursion, please go to: Understanding and Implementing Recursion

Write test cases

Next, we take all the boundary conditions into account to verify that the above code executes correctly.

import IntegerPower from ".. /IntegerPower.ts";

const powerHandler = new IntegerPower();
const result1 = powerHandler.power(5.6);
const result2 = powerHandler.power(3, -4);
const result3 = powerHandler.power(0.0);
const result4 = powerHandler.power(0.3);
const result5 = powerHandler.power(0, -3);
console.log(result1);
console.log(result2);
console.log(result3);
console.log(result4);
console.log(result5);

Copy the code

The running result is as follows:

Project code

The sample code in this article can be moved to:

  • IntegerPower.ts
  • integerPower-test.ts

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in the magic programmer public number, without permission to prohibit reprinting 💌