preface

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

Quick powers

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.

1.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

1.2 Idea 2: Binary splitting

Let’s take x14 as an 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

1.3 the reference

Pecco- Algorithm Study Notes (4) : Fast powers

[Day and Night ACM Notes] Miscellaneous – quick power

Two, fast power modulus

2.1 Modular operation rules

  • (a + b) % p = (a % p + b % p) % p
  • (a – b) % p = (a % p – b % p + p) % p
  • (a * b) % p = (a % p * b % p) % p
  • ab % p = ((a % p)b) % p

From this law, the congruence property can be derived

2.2 FAQ Scenarios

We’ll often see the output modulo x. This topic generally examines two points:

  • On the basis of the original algorithm, one more modulus operation to check your grasp of the rule of modulus operation
  • In big data, data grows so fast that 64-bit or even 128-bit reshaping cannot be represented
    • “Sword points to Offer” 14-ii. Cut the ropeIt’s a typical question
      • Answer key

2.3 Use fast power to control the range of data

14-ii. In the rope cutting process, the range of power operation results is not more than 1_000_000_007 through fast power and combined with the rule of modular operation.

func modPow(_ x: Int._ n: Int) -> Int {
    var res = 1
    var x = x
    var n = n
    
    while n > 0 {
        if n & 1 = = 1 {
            res * = x
            res % = 1 _000_000_007 // Limit the data range
        }
        x * = x
        x % = 1 _000_000_007 // Limit the data range
        n > > = 1
    }
    
    return res
}
Copy the code