This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Hi 👋

  • Wechat: RyukieW
  • 📦 Technical article archive
  • 🐙 making
My personal project Mine Elic endless sky ladder Dream of books
type The game financial
AppStore Elic Umemi

A, the title

Implement POw (x, n), that is, calculate x to the NTH power function (i.e., xn). Library functions should not be used and large numbers should not be considered.

Example 1:

Input: x = 2.00000, n = 10 Output: 1024.00000Copy the code

Example 2:

Input: x = 2.10000, n = 3 Output: 9.26100Copy the code

Example 3:

Input: x = 2.00000, n = 2 output: 0.25000 explanation: 2 ^ (2) = 1 / (2 ^ (2)) = = 0.25 a quarterCopy the code

Tip:

-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104Copy the code

Source: LeetCode

Link: leetcode-cn.com/problems/sh…

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Two, fast power

The power operation is one of the most common operations we use. If we want to take x to the NTH power, then of course we’re going to write an NTH power cycle, and then multiply it out. The complexity of this power operation is order N.

var res = 1
for _ in 0..<n {
    res * = x
}
return res
Copy the code

So is there a faster way to do this?

In the computer field, there is a common fast power algorithm: Montgomery Reduction algorithm. I’m going from order N to order logN.

2.1 Idea 1: Recursion

  • If N is even, you can take xN over 2 and square it.
  • If N is odd, we can take x of N minus 1 over 2, square it, and multiply it by x

The basic idea of fast powers is these two.

The same idea applies to xN over 2, xN minus 1 over 2, and every time you divide the exponent by 2, you reduce the complexity by half until the exponent is 1.

Swift implementation

  • I don’t think about big numbers here, but it’s just an idea
func quickpow(_ x: Int._ n: Int) -> Int {
    if n = = 0 {// Until the final exponent is 0
        return 1
    }
    let res = quickpow(x, n/2)
    if n%2 ! = 0 {// N is odd
        return res * res * x
    }
    // n is even
    return res * res
}
Copy the code

2.2 Idea 2: Binary splitting

We take the x14For example.

14(10)1110(2)1000(2)100(2)10(2)

To make it more intuitive, go the other way:

1110(2)10(2)100(2)1000(2)

Corollary:

  • Let x to the NTH be equal to res
    • 1: In the binary form of the exponent N, x multiplies itself once, starting from the lowest position by one place to the left (consistent with the exponent N moving one place to the left)
    • If the current bit is 1
      • The multiplication of the value b, xb, from the current bit a to the lowest bit, with all the middle bits set to 0
    • If the current bit is 0
      • Perform 1
    • I keep going until the exponent N is equal to 0
The current position Index b res
1110 0 x0(2)
1110 10 x10(2)
1110 100 x10(2) * x100(2)
1110 1000 x10(2) * x100(2) * x1000(2)

Swift implementation

  • I don’t think about big numbers here, but it’s just an idea
func quickpow(_ x: Int._ n: Int) -> Int {
    var res = 1
    var x = x
    var n = n
    
    while n > 0 {
        if n & 1 = = 1 { // If the current end of n is 1
            res * = x // Res times the current x
        }
        x * = x// The current exponent is shifted one bit to the left
        n > > = 1// Let's move n to the right one place, so we want n over 2
    }
    
    return res
}
Copy the code

Third, the problem solving

The conditions in this case are slightly different from the examples in the quick powers described above, so adjust them.

3.1 the recursive

func myPow(_ x: Double._ n: Int) -> Double {
    // Return the result directly
    if x = = 0 || x = = 1 {
        return x
    }
    else if x = = -1 {
        return (n & 1 = = 1 ? -1 : 1)}if n = = 0 {
        return 1
    }
    else if n < 0 {
        return myPow(1/x, -n)
    }
    else if n = = 1 {
        return x
    }
    
    let temp = myPow(x, n >> 1)
    return temp * temp * ((n & 1 = = 1) ? x : 1)}Copy the code

3.2 the recursion

func myPow(_ x: Double._ n: Int) -> Double {
    // Return the result directly
    if x = = 0 || x = = 1 {
        return x
    }
    else if x = = -1 {
        return (n & 1 = = 1 ? -1 : 1)}if n = = 0 {
        return 1
    }
    
    var ans: Double = 1
    var power = abs(n)
    var newX = x
    while power > 0 {
        if power & 1 = = 1 {
            ans * = newX
        }
        newX * = newX
        power = power >> 1
    }
    return n < 0 ? 1 / ans : ans
}
Copy the code