Detailed explanation of fast power algorithm that migrant workers must know

preface

What is fast power?

  • As the name suggests, the fast power is the n-th power of the fast base.

How fast?

  • Its time complexity is O(log ν n), which greatly improves the efficiency compared with the simple O(n).

How good is it?

  • Fast power belongs to the category of number theory. It was originally a classic ACM algorithm, but now factories have higher and higher requirements for the algorithm, and the application scenario of fast power is much lower, and it has been greatly improved compared with the naive method. Therefore, mastering fast power algorithm is a necessary requirement for a more qualified engineer!

Let's take a detailed look at the fast power algorithm!

Introduction to fast power

Let's look at a question first:

Probe into

First of all, let me ask you a question. If you ask for (2 ^ 10)% 1000, you may write as follows:

int va=1;
for(int i=0;i<10;i++)
{
  va*=2;
}
System.out.println(va%10000);

Familiar 1024 is no problem. It has been calculated 10 times in total. But what if you count (2 ^ 50)% 10000?

You may be secretly happy, sample, so you want to embarrass me? I know that int has only 32 bits. If 50 bits are out of range, the value will be out of range. I can use long this time. Long has 64 bits!

long va=1;
for(int i=0;i<50;i++)
{
  va*=2;
}
System.out.println(va);
System.out.println(va%10000);

The result comes out after 50 calculations. Just when you are secretly happy, another fatal problem comes: let you calculate (2^1e10)%10000 and forbid you to use Java large number classes. You are distressed and overwhelmed. At this time, little brother bigsai asked you to take module operation under Baidu, and then you suddenly realized that you wrote several formulas on the paper:

(a + b) % p = (a % p + b % p) % p  (1)
(a - b) % p = (a % p - b % p ) % p (2)
(a * b) % p = (a % p * b % p) % p  (3)
a ^ b % p = ((a % p)^b) % p        (4)

You're smart enough to see the rules at a glance:

(a * b) % p = (a % p * b % p) % p   (3)
(2*2*2···*2) %1e10=[2*(2*2···*2)]%1e5=(2%1e5)*(2*2···*2%le5)%1e5

With this recursion, you know: every multiplication takes a module. Tactfully, you pia pia write the following code, but you find another problem: why can't you run out?

We workers need to have a general concept of computer speed and value. Different operations in the loop body take different time, so you need to be very careful when your program cycles to 1e6 or 1e7. If there are many loop logic or operations, it may be very, very slow.

Fast power exploration

You are smart and unwilling to fail. Start to study the law of numbers and write this formula on your hands, arms and small notes. Eating and sleeping are watching:

Then you suddenly discover the mystery. The power of n can be divided into a square, and the power of n/2 remains after calculation:

Now you have understood what fast power is about, but you may be a little ahead, but you still told me a lot:

Fast power realization

As for the fast power has been understood, how should we implement this algorithm?

Yes, there are recursive and non recursive implementations, but recursion is used more. When implementing, just pay attention to parity and stop conditions. The odd number problem can be transformed into an even number problem:

2*2*2*2*2=2 * (2*2*2*2) Odd number problem can be transformed into even number problem.

Here, the recursive solution is as follows:

long c=10000007;
public  long divide(long a, long b) {
		if (b == 0)
			return 1;
		else if (b % 2 == 0) //Even case
			return divide((a % c) * (a % c), b / 2) % c;
    else//Odd case
			return a % c * divide((a % c) * (a % c), (b - 1) / 2) % c;
	}

It is not difficult to implement non recursively. Just control the loop conditions:

//Find a^b%1000000007
long c = 1000000007;
public  long divide(long a, long b) {
  a %= c;
  long res = 1;
  for (; b != 0; b /= 2) {
    if (b % 2 == 1)
      res = (res * a) % c;
    a = (a * a) % c;
  }
  return res;
}

For non recursion, you may be a little vague about why res is not assigned in the even case. Here are two points:

  • In the case of an odd number, res is simply a collection multiplied by the single a at that time
  • In the end, b will drop to 1, and a will be multiplied by res. don't worry about missing it
  • The ideal state is always an even number, so you can directly obtain the modulus value of a.

If you still don't understand, you can use this figure to explain:

Matrix fast power

You think it's over? Although the main content of fast power is the above, there are always many cattle who can find a very interesting law - matrix fast power. If you haven't heard of it, I suggest you take a closer look.

We all know the rules of Fibonacci sequence:

The first Fibonacci sequences are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Fibonacci can be seen from the recursive formula that it is an exponential growth, so a few more figures are explosive growth, so it often requires the results of the last few digits. With the previous modular operation formula overflow is not a problem, but if n is very, very large, how to calculate quickly has become a new problem.

Let's look at the following set of formulas:

f(n+1) = f(n)   + f(n-1)
f(n)   = f(n)

If f(n) and f(n-1) are put into a matrix (one row and two columns): [f(n+1),f(n)] can find any law between [f(n),f(n-1)]?

The answer to the above formula is to know the law

[f(n+1),f(n)]
=[f(n)+f(n-1),f(n)]

                 [1  1]
=[f(n),f(n-1)]  *      
                 [1  0]
                 
                 [1  1] [1   1]
=[f(n-1),f(n-2)]*      *
                 [1  0] [1   1]  

=·······           

So now you can know its law. In this way, iterate until f(2),f(1) is exactly 1, so the calculation of Fibonacci is:

The matrix has many powers, so you can use fast power. The principle is the same. You only need to write a matrix multiplication. The following provides a template for matrix fast power to find the last three digits of Fibonacci's n term. You can take this to try the problem of poj3070.

public int Fibonacci(int n)
    {
        n--;//The matrix is two terms
        int a[][]= {{1,1},{1,0}};//Matrix with fast power
        int b[][]={{1,0},{0,1}};//The matrix for storing odd numbers and results of missing orders, initially the identity matrix
        int time=0;
        while(n>0)
        {
            if(n%2==1)
            {
                b=matrixMultiplication(a, b);
            }
            a=matrixMultiplication(a, a);
            n/=2;
        }
        return b[0][0];
    }
 public  int [][]matrixMultiplication(int a[][],int b[][]){//
        int x=a.length;//a[0].length=b.length is the condition
        int y=b[0].length;//Make sure there are several in each row
        int c[][]=new int [x][y];
        for(int i=0;i<x;i++)
            for(int j=0;j<y;j++)
            {
                //Each element needs to be identified
                //c[i][j];
                for(int t=0;t<b.length;t++)
                {
                    c[i][j]+=(a[i][t]%10000)*(b[t][j]%10000);
                    c[i][j]%=10000;
                }
            }
        return c;
    }

epilogue

This article will be finished here. In fact, there are more contents of fast power, especially the fast power of matrix, which will have various ingenious deformations, but it has something to do with mathematics. It is really difficult to point algorithm and mathematics these days. So you should absorb the content of this article and let my efforts for so long play a role.

If you have any questions and don't know how to understand, you are welcome to talk to me in private. I also hope you can point and see. Your support is the continuous driving force of my efforts.

Pay attention to bigsai and reply to bigsai to receive dry goods resources. See you next time, migrant workers!

Posted by janm2009 on Mon, 09 May 2022 11:41:41 +0300