Today also learned an algorithm, fitfully spent two hours to understand, have to sigh, the algorithm is really too strong, simplify super many steps, too strong, too strong, too strong πŸ‘

First of all, what is the problem solved by fast power? The core problem is to solve the problem of “unbearable number” of computers. Imagine a scenario, if you were asked to calculate the last three values of 21202^{120}2120, what would you do? You might say “so easy”, is your solution hard, smart, or smart? Listen to me:

1. Power function hard calculation

The hard-computing code using the POW function is as follows:

#include<cmath>
int main(a){
    long long int x;
    x = pow(2.120);
    cout<<x<<endl;
  	cout<<x%1000<<endl;
    return 1;
}

/ / print
/ / - 9223372036854775808
/ / - 808


Copy the code

Why? The size of the int data type is the size of the int data type. In 64-bit compilers, int generally takes 4 bytes, long long ints take 8 bytes, remove the first symbol bit, The βˆ—8βˆ’1βˆ’1=92233720368547758072^{8*8-1}-1=922337203685477580728βˆ—8βˆ’1βˆ’1=9223372036854775807, And 21202^{120}2120 is far more than this number, so the exhausting computer can not calculate it, let alone how to calculate its last three.

Let’s improve on that, and use the one-wave modulus theorem to optimize

2, take the modular theorem cunning calculation

Take modulus operation to solve a number of large numbers multiplied by the result is too large (computer does not support) and can not take a few after the problem, take modulus theorem I also listen to for the first time, after looking at the discovery is really cattle, not loss is a mathematical theorem. Here is not detailed, specific can see my == another article ==, the specific content of the modulus theorem:

(a + b) % p = (a % p + b % p) % p (1) (a - b) % p = (a % p - b % p) % p (a - b) % p = (a % p - b % p) % p (2) (a * b) % p = (a % p * b % p) % p (3A ^b % p = ((a % p)^b) % p (4)Copy the code

(a * b) %p = (a%p * b%p) %p = (a%p * b%p) %p = (a%p * b%p) %p = (a%p * b%p) %p

Code to use modulo:

int main(a){
    long long int result=1;
/ / x = pow (2120);
    clock_t start_time = clock(a);for(int i=0; i<120; ++i){ result = result*2%1000;
    }
  	result = result % 1000;
  
    clock_t end_time = clock(a); cout<<result<<endl; cout<<"Calculate the time taken:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
  	// The difference between start_time and end_time is calculated by the number of clock units it takes the CPU to run the program, and then divided by CLOCK_PER_SEC.
    return 1;
}

/ / print
/ / 576
// The calculation takes time 3e-06

Copy the code

This speed also too 6, and still calculate a result, mathematical theorem is really too strong, not bear me love it all the time πŸ˜‚, although the most important test in the life is mathematics test to fail.

Feel the power of a mathematical theorem, but that’s enough? The modulus theorem only controls the data within a certain number of digits so that the number can be calculated, but it does not simplify the number of calculations (still 120 times). It would be better to have an algorithm that simplifies the calculation steps. As the saying goes, there is no fastest only faster πŸ˜†. Please welcome today’s protagonist, the fast power algorithm to shorten the number of calculations.

3, fast power algorithm intelligent calculation

When I saw the explanation of the algorithm, I stood up, as if I saw a new world beckoning to me, that is the algorithm. The algorithm is really strong, it can take a complex problem, reduce it to small problems, and solve it in a loop, and it’s very fast.

All right, cut to the chase and get down to business. First of all, I write articles to exercise my writing ability, and deepen the understanding of knowledge, maybe my explanation is not very clear. If you don’t understand the friends, you can directly see the reference article at the bottom of the article, the big guy wrote this fast power algorithm more detailed, there is a need to see.

3.1. What is fast power algorithm?

Fast power algorithm, also known as Binary Exponentiation, can greatly reduce the calculation steps, so as to improve the speed of calculation. It is a small technique to calculate in lognlog_nlogn time, while violent calculation requires NNN time.

3.2 Algorithm description

For example, we calculate ana^nan, which equals an1βˆ—an2… βˆ— ansa ^ {n1} * a ^ {n}… * a ^ {ns} an1 βˆ— an2… βˆ—ans, where n=n1+n2+…… +nsn = n1 + n2 +…… + nsn=n1+n2+…… + ns. But when n gets really big, it’s going to take a lot of calculation, what’s called an exponential explosion. A2b =(ab)2a^{2b}=({a^b})^2a2b=(ab)2 = 4 ^ 2 ^ {400} {200} = 16 ^ {100} =… 2400 = 4200 = 16100 =… , the calculation suddenly lost 200 steps, 300 steps…… Is there any efficiency.

Now that we know that squaring can shorten the calculation, we can represent the powers in binary terms. For example, 313=3(1101)2=38βˆ—34βˆ—313^{13}=3^{(1101)_2}=3^8*3^4*3^1313=3(1101)2=38βˆ—34βˆ—31.

Do you realize that only the bits that are 1 are multiplied inside, and the zeros are skipped. So we just need to convert base 10 to base 2 (continuously divide the remainder of 2 until the quotient is 0), and we can get the binary number corresponding to the power number. If one of the binary bits is a 1, the number is multiplied into the result and the base is doubled; If it’s 0, then the base doubles. But if you look at the derivation, it’s a little convoluted here, so let’s go through it.

For a binary, the base is 3
13/2 = 6 δ½™1	3*3=9 result=result*3,base=base*base
6/2 = 3 δ½™0	Base = 81base =base*base
3/2 = 1 δ½™1	Result =result*3,base=base*base
1/2 = 0 δ½™1	6561*6561 result=result*3,base=base*base
# so the corresponding binary is 1101

# 2, the corresponding computation code Python
def quick(base, power) :
    result = 1
    b = power
    while(b>0) :if b&1:   If b%2 == 1: odd
            result = result * base
        base = base * base
        b >>= 1      So this is the same thing as b is equal to b over 2, so let's take half of b
    print(result)

quick(3.13)

# print
# 1594323
Copy the code

You think this is the end of it? There is still a step to go. Fast powers only shorten the number of calculations, but it does not solve the problem of calculating the last three digits of high powers (e.g. 21202^{120}2120). And you might think, well, if you add in the modulo, you’re going to shrink everything, and you’re going to be able to figure it out.

Yes, that’s it, fast power algorithm + modulus theorem a perfect cp match, a wave of c++ code:

#include<iostream>
#include<ctime>
using namespace std;

int main(a){
    long long int result=1;
    int base = 2,power=120;
    clock_t start_time = clock(a);while(power>0) {if(power & 1){
            result = result*base%1000;
        }
        base = (base*base)%1000;
        power >>= 1;
    }
  	result = result%1000;
  	
    clock_t end_time = clock(a); cout<<result<<endl; cout<<"Calculate the time taken:"<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
    cout<<"CPU clock per second:"<<CLOCKS_PER_SEC<<endl;
    return 1;
}

/ / print
/ / 576
// Time to calculate: 1e-06
// CPU clock per second: 1000000

Copy the code

Wow, finally finished, good headache πŸ˜‚~

Conclusion:

Algorithm is really strong, very efficient, love, hard to learn algorithm in ~

Reference article:

Blog.csdn.net/qq_19782019…

Oi-wiki.org/math/quick-…