This is the 28th day of my participation in the August Text Challenge.More challenges in August

Pow(x, n)

Implement POW (x, n), that is, compute x to the NTH power (that is, x to the n).

The problem solving

I’m going to exponentiate the product of n x’s.

We can use the method of multiplication to calculate, set a value of 1, multiply the number n times x, the number is the result. However, this one is rated as medium difficulty, which is a surefire way to run out of time (I tried it out for rigor) :

Due to the large number of powers, it is too much to use the method of continuous multiplication to calculate, so we spend memory space to store part of the calculated values, reduce the calculation times, and achieve the effect of using space for time.

At the beginning, the calculation process we used was as follows:

1 -> x^1 -> x^2 -> x^3 -> … -> x^n

This method, although it runs out of time, is the most space-efficient method. Since the calculation rule of power function is very clear, we can spend extra memory space to use divide-and-conquer algorithm to simplify the process as follows:

x^2 -> x^4 -> x^8 -> x^16 -> … -> x^n

Each term goes to the next term, and you just multiply the terms, and this method grows exponentially, and it converges quickly for large n, and it’s very effective.

However, it is impossible for n to be all powers of 2 or even, so we need to further improve the process to adapt it to other n values. The optimization is as follows:

  1. Record the value of n, changing n / 2 each time you move to the next term.

  2. If n is divisible by 2 (even), then the next term is t * t; If n is not divisible by 2, the next term is x * t * t, which means that multiplying by one more x makes n even.

  3. Repeat operation 1, 2, take n=1 as the boundary condition, if n=1, it indicates the end of the power operation, and return the x value at this time.

Code implementation

Use recursion to do the above and add n = 0 and x = 1 boundary conditions.

In addition, n < 0 May occur, take the reciprocal of x and take the absolute value of n, and other steps remain unchanged:

func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n == 1 || x == 1.0 {
        return x
    }

    if n < 0 {
        n *= - 1
        x = 1.0 / x
    }

    if n % 2= =0 {
        return myPow(x * x, n / 2)}return x * myPow(x * x, n / 2)}Copy the code

Submit the results