Fast Power

define

Exponentiating squaring, also known as exponentiating squaring, is a way to quickly calculate a positive integer to the NTH power of a base. The time complexity is O(logn)O(logn)O(logn)

The calculation of power

So before we start talking about fast powers, let’s think about, if you had to calculate ABA ^ BAB, how would you do it?

So what we do is we multiply a times itself b times.

The code is implemented as

/ * * * *@param {integer}} base a *@param {integer} B * /
function iterativePower(a, b) {
	let result = 1;
	while (b>0) {
		result *=a;
		b--;
	}
	return result;
}
Copy the code

The time complexity of this method is O(N), where N is the exponent, which is b in the example above

So is there a more efficient way to solve this problem?

The answer is there and that’s the way we’re going to do it today, fast powers. This is useful when the exponents are large. For example, matrix power, cryptography are very good use.

Fast power base method

The change is based on the observation that for positive integers n, we have

This method uses the bits of the exponent (the bits of binary, hereinafter referred to as “bits”) to determine which powers to compute.

For example, if we calculate x13x^{13}x13. The binary power of 13 is 1101. The bits are used in left-to-right order. The exponent has four bits, so we do four iterations.

First, we initialize the result to 1.

1. R please (r2 = x0) r \ leftarrow r ^ 2 (= x ^ 0) r please r2 (= x0), the first = 1, so please calculate r r ∗ (= x1) r \ leftarrow r * x x (= x ^ 1) r please r ∗ x (= x1).
2. R please (r2 = x2) r \ leftarrow r ^ 2 r (x ^ 2 =) please r2 (= x2), the second = 1, so please calculate r r ∗ x (= x3) r \ leftarrow r * x (= x ^ 3) r please r ∗ x (= x3).
3. R ← R2 (=x6)r\leftarrow r^2(=x^6)r← R2 (=x6), the third bit = 0, so there is no need to calculate this step.
4. R please (r2 = x12) r \ leftarrow r ^ 2 (= x ^ {12}) r please r2 (= x12), the fourth = 1, so please calculate r r ∗ x (= x13) r \ leftarrow r * x (= x ^ {13}) r please r ∗ x (= x13).

In mathematics, ←\leftarrow← corresponds to the left which can be deduced from the right.

The code for fast powers is shown below

The recursive version

/ * * * *@param {integer}} base a *@param {integer} B * /
function fastPower1(a, b) {
  if ((b === 0)) return 1
  if ((b === 1)) return a;
  if (b % 2= = =0) return fastPower1(a * a, b / 2)
  if (b % 2! = =0) return a * fastPower1(a * a, (b - 1) / 2)}Copy the code

Tail recursion

An enhanced version of recursion, which no longer holds variables during computation in the call stack, is considered an enhanced version of recursion.

function exp_by_squaring(x, n) {
  return exp_by_squaring2(1, x, n);
}
function exp_by_squaring2(y, x, n) {
  if (n === 0) return y;
  if (n === 1) return x * y;
  if (n % 2= = =0) return exp_by_squaring2(y, x * x, n / 2);
  if (n % 2= = =1) return exp_by_squaring2(x * y, x * x, (n - 1) > >1);
}
Copy the code

The iterative version

Anything we can do recursively we can do iteratively, it’s good performance, but it’s not as easy to understand as recursion

function exp_by_squaring_iterative(x, n) {
  let y = 1;
  if (n === 0) return 1;
  while (n > 1) {
    if (n % 2= = =0) {
      x *= x;
      n /= 2;
    } else {
      y *= x;
      x *= x;
      n = (n - 1) > >1; }}return x * y;
}
Copy the code

Bit operation optimization version

This version is based on the property that n&1 can get whether the end of n is 1 or not to make parity judgment.

function quickPow(a, n) {
  let base = a,
    res = 1;

  while (n) {
    if (n & 1) {
      res *= base;
    }
    base *= base;
    n >>= 1;
  }
  return res;
}
Copy the code

---

Basic knowledge of related content

Question about how to display larger numbers

If the result is large, such as 2(1000)2^(1000)2(1000), we modulo 1E9 + 7 for the result of each step in the calculation process to prevent the data from crossing the boundary. As for the reason, it is a TLDR story

How to convert decimal to binary?

Decimal integers to binary integers Decimal integers are converted to binary integers using the “mod 2, reverse order” method. Specific approach is: use 2 to divide decimal integer, can get a quotient and remainder; Then divide the quotient by 2, and another quotient and remainder will be obtained, and so on until the quotient is less than 1. Then, the remainder obtained first as the lowest significant bit of the binary number, and the remainder obtained later as the highest significant bit of the binary number are arranged in order.

789=1100010101(B)

789/2=394 remainder 1, 10th place

394/2=197 remainder 0 ninth place

197/2=98 remainder 1 is the eighth place

98/2=49 remainder 0 is the seventh digit

So 49/2 is 24, 1 is the sixth place

24/2=12 remainder 0 is the fifth digit

12/2=6 remainder 0 is the fourth digit

6/2=3 remainder 0 is the third digit

3/2 is equal to 1, left 1, second place

1/2 is equal to 0 remainder 1 is the first digit

Principle:

As we all know, the base of binary is 2, and the 2 we divide when we decimalize binary is its base. Talking about its principle, we have to talk about the concept of position weight. The value represented by each numeric symbol in a base counting system represents the value of the numeric symbol multiplied by a constant associated with the numeric symbol, which is called the “bit weight”. The magnitude of the bit weight is based on the base, and the ordinal number at the position of the numeric symbol is an integer power of the exponent. The hundreds, tens, ones, and tenths of decimal numbers have weights of 10 to the second, 10 to the first, 10 to the zero, and 10 to the -1, respectively. Binary number is 2 to the NTH power.

Summation by weight expansion is exactly the way to de-decimalize decimal.

Now let’s talk about the principle, take an example of converting A decimal integer into A binary integer, assuming that the binary number of decimal integer A is in the form of EDCBA, then expand by weight using the above method, get

A = A (20) + b (21) + c (22) + d (23) + e (24) A = A (2 ^ 0) + b (2 ^ 1) + c (2 ^ 2) + d (2 ^ 3) + e (2 ^ 4) A = A (20) + b (21) + c (22) + d (23) + e (24) (and not behind it is the process of decimal?)

Assuming the number is not converted to binary, divide by base 2

$A/2=a(2^0)/2+b(2^1)/2+c(2^2)/2+d(2^3)/2+e(2^4)/2$

Note: A is not divisible into 2, but the others are divisible, because they all contain 2, and A times 1, it does not contain a factor of 2, only the remaining.

Dealer:

B (20) + c (21) + d (22) + e (23) b (2 ^ 0) + c (2 ^ 1) + d (2 ^ 2) + e (2 ^ 3) b (20) + c (21) + d (22) + e (23), divided by base the remaining 2 b, and so on.

When the number can no longer be divided by 2, the remainder of the a digit is lower than the original digit and the remainder is higher, so write all the remainder in reverse. Just edcba.

The index

Exponentiation by squaring

Fast power