# 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