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-…