# [algorithm] Analysis on the use of fast power operation in JavaScript # start

Find the n-th power of x (just talk about n nonnegative first)

## Violent solution

x n = x ⋅ x ⋅ x ⋅ ⋅ ⋅ x x^{n} = x · x · x ··· x xn=x ⋅ x ⋅ x ⋅ ⋅ x (multiply n x)

[violence solution] key steps

```let result = 1
while(n > 0){
result *= x
n--
}
```

Cycle n times, time complexity is O(N)

## Counting

Key steps of [fast power]

Let's take an example to find the 100th power of x

The solution to violence is

x 100 = x ⋅ x ⋅ x ⋅ ⋅ ⋅ x x^{100} = x · x · x ··· x x100=x ⋅ x ⋅ x ⋅ ⋅ x (multiply 100 x)

Because the binary of 100 is 1100100, so

100 = 0 ⋅ 2 0 + 0 ⋅ 2 1 + 1 ⋅ 2 2 + 0 ⋅ 2 3 + 0 ⋅ 2 4 + 1 ⋅ 2 5 + 1 ⋅ 2 6 100 = 0·2^0 + 0·2^1 + 1·2^2 + 0·2^3 + 0·2^4 + 1·2^5 + 1·2^6 100=0⋅20+0⋅21+1⋅22+0⋅23+0⋅24+1⋅25+1⋅26

that is

100 = 2 2 + 2 5 + 2 6 100 = 2^2 + 2^5 + 2^6 100=22+25+26

So we can simplify the solution formula

x 100 = x 2 2 ⋅ x 2 5 ⋅ x 2 6 x^{100} = x^{2^2} · x^{2^5} · x^{2^6} x100=x22⋅x25⋅x26

```let result = 1
// When n === 0, there is no loop, and the result is result === 1
while (n > 0) {
// Judge whether the current lowest order is 1
if ((n & 1) === 1) result *= x
x *= x
n >>>= 1 // Move right without symbol to delete the lowest order
}
```

loop l o g 2 N log_2 N log2 ＾ N times, and the time complexity is O(logN)

# LeetCode 50. Pow(x, n)

Let's look at a power problem on LeetCode 50. Pow(x, n)

The key step is the same, mainly considering the case of negative power

```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
};
```

There is also a more concise code. I named it preprocessing

```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
};
```

Naturally, the first is post-processing. Find the positive solution, and then take a reciprocal at the end It can be seen that the efficiency of post-processing is higher than that of first processing. This is the comparison when I submitted it for the first time, but I tried it again today The result is like this. The efficiency of JS in LeetCode is really a mystery~
I won't discuss too much here. I have the opportunity to study it again

# Find the last digit of the power of a large number

Let's increase the difficulty: the two non negative numbers passed in are strings, which may be very large numbers;
At the same time, simplify the topic again: just return the last digit of the result

[requirements] requirements a b a^b The last digit of ab, a and b may be very large

[analysis]
seek a b a^b The last digit of ab only requires the last digit. No matter how large a is, we only need to calculate the last digit of a and c c b c^b The result of cb is enough

```let a = +str1[str1.length - 1];
```

The next step is the process of fast exponentiation

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

Since only the last bit is required, the single digit is obtained by% 10 in the operation (result and a)

So the complete code is 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
```

# String repeated n times

To expand, let's talk about a string str repeated count times. We use the idea of fast power

See my previous blog for more details
[youth training camp] teacher Yueying told me four skills for writing 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) // **********
```

# summary

Using fast exponentiation can reduce the time complexity of exponentiation

The fast power has a unified form and can be expanded

Keywords: Javascript Algorithm leetcode

Added by Eugene on Mon, 20 Sep 2021 12:09:12 +0300