This is the 9th day of my participation in the August Wen Challenge.More challenges in August

start

To the NTH power of x.

Violent solution

Xn ⋅ ⋅ = x x x ⋅ ⋅ ⋅ xx ^ {n} = · · · · · XXN = x x x x ⋅ ⋅ ⋅ x x ⋅ ⋅ x (n x multiplication)

【 Violent solution 】 key step

let result = 1
while(n > 0){
    result *= x
    n--
}
Copy the code

N times, order n.

Fast power

The key step of fast Power

So let’s take an example of x to the 100

The violent solution is

X100 ⋅ ⋅ = x x x ⋅ ⋅ ⋅ xx ^ {100} = · · · · · xx100 = x x x x ⋅ ⋅ ⋅ x x ⋅ ⋅ x 100 x (multiply)

Because the binary of 100 is 1100, 100, so

$100 = 0, 2 ^ 0 + 0, 2 ^ 1 + 1, 2 ^ 2 + 0, 2 ^ 3 + 0, 2 ^ 4 + 1, 2, 2 ^ 6 ^ 5 + 1$

That is

$100 = 2^2 + 2^5 + 2^6$

So we can simplify the formula

$X ^{100} = x^{2^2} · x^{2^5} · x^{2^6}$

let result = 1
// result == 1 when n === 0
while (n > 0) {
    // Check whether the current lowest value is 1
    if ((n & 1) = = =1) result *= x
    x *= x
    n >>>= 1 // Unsigned right move to delete the lowest level
}
Copy the code

Log 2n log 2n log 2n times, order logN.

LeetCode 50. Pow(x, n)

Let’s look at a exponentiation problem in LeetCode 50. Pow(x, n)

The key step is the same, the main thing is to think about negative powers

var myPow = function(x, n) {
    let result = 1

    let flag = false
    if(n < 0){
        flag = true
        n = -n
    }

    while (n > 0) {
        if ((n & 1) = = =1) result *= x
        x *= x
        n >>>= 1
    }
    if(flag){
        result = parseFloat(1/result)
    }
    return result
};
Copy the code

There’s a little bit cleaner code that I’m going to call pre-processing

var myPow = function(x, n) {
    let result = 1

    if(n < 0){
        x = parseFloat(1/x)
        n = -n
    }

    while (n > 0) {
        if ((n & 1) = = =1) result *= x;
        x *= x
        n >>>= 1;
    }
    
    return result
};
Copy the code

The first, of course, is post-processing, where you solve for the positive number, and then you take an inverse at the end

As you can see, post-processing is more efficient than pre-processing, and this is the comparison I made when I first submitted it, but I tried it again today

The efficiency of JS in LeetCode is a mystery. I won’t discuss it too much here, but I’ll look into it later

Take the last digit of a larger power

Let’s make it harder: The two non-negative numbers passed in are strings, which can be very large numbers; At the same time, simplify the problem ~(escape): return the last digit of the result

[requirement] find the last digit of ABA ^bab, a and b may be large

【 答 案 】 we need to calculate the CBC ^ BCB of the last digit of A, no matter how big a is

let a = +str1[str1.length - 1];
Copy the code

And then you have rapid exponentiation

while (b > 0) { 
    if ((b & 1) = = =1) result = (result * a) % 10; 
    a = (a * a) % 10; 
    b >>>= 1; 
}
Copy the code

Since only the last digit is needed, %10 is taken to the units digit in the operations (result and a)

So the complete code looks like this

function yk(str1, str2) {
  let a = +str1[str1.length - 1];
  let b = +str2;
  if (a === 0) return 0;
  let result = 1;

  while (b > 0) {
    if ((b & 1) = = =1) result = (result * a) % 10;
    a = (a * a) % 10;
    b >>>= 1;
  }

  return result;
}

const res = yk("24979"."8");
console.log(res); / / 1
Copy the code

The string is repeated n times

To expand, let’s take a string STR repeated count times, and we use the idea of fast powers

More details can be found in my previous blog post [Youth Training] where Yueyin told me about the four tips for writing good JavaScript code — style first

function repeat(str, count) {
  var result = "";
  while (count > 0) {
    if ((count & 1) = =1) result += str;
    count >>>= 1;
    str += str;
  }
  return result;
}
const res = repeat("*".10)
console.log(res) / / * * * * * * * * * *
Copy the code

conclusion

Using fast powers can reduce the time complexity of exponentiation

Fast powers have a unified form and can be extended