Algorithm Notes Learning-Fast Power

Algorithm Notes Learning --- Fast Power Introduction:

Fast Power .Let's look at a question first:
Fast Power .Given three positive integers a, b, m (a<10, b<10, 1This can be written as long as you have learned to loop, like the following code, the time complexity is O(b):
typedef long long LL;
LLpow ( LL a , LL b , LL m)
{
LL ans = 1 ;
for ( int i = 0 ;i< b;i ++)
{
ans = ans * a % m;
}
return ans ;
}
for using long long instead of int in the code is to prevent overflow after multiplying two int variables.
Next we investigate a further question:
Given three positive integers a, b, m (a<103, b<1018, 1For this problem, it is obviously not feasible to follow the above method. The complexity of O(b) is very difficult to support b < 108, let alone 1018.
fast powers is used here , which is based on the idea of division, so it is often called the act of dichotomy. Fast powers are based on the following facts:
①If b is odd, then there is ab=a * a(b-1).
②If b is even, then there is ab=ab/2 * ab/2.
Obviously, the case that b is odd can always be converted to the case that b is even in the next step, and the case that b is even can always be converted to the case of b/2 in the next step. In this way, after the log(b) level number of transformations, b can be changed to 0, and any positive integer to the 0th power is 1.
For example, if you need to find 2^10:
① For 210, since the power of 10 is an even number, you need to find 25 first, and then 210=25 * 25.
② For 25, since the power of 5 is an odd number, 24 needs to be calculated first, and then 25 = 2 * 24.
③ For 24, since the power of 4 is an even number, 22 needs to be calculated first, and then 24=22 * 22.
④ For 22, since the power of 2 is an even number, 21 needs to be calculated first, and then 22=21 * 21.
⑤ For 21, since the power of 1 is an odd number, 20 needs to be calculated first, and then 21=2 * 20.
⑥ 20=1, and then reverse the calculation from bottom to top.
This is obviously the idea of recursion, so the recursive writing method of fast power can be obtained , and the time complexity is O( logb ):
typedef long long LL;
//Seek a^b % m , recursive writing
LL binaryPow ( LL a , LL b , LL m)
{
if (b== 0 ) return 1 ; //If b is 0, then a^0=1
//b is odd, convert to b-1
if ( b % 2 == 0 ) return a * binaryPow (a , b -1 , m) % m;
else //b is even, convert to b/2
{
LL mul = binaryPow ( a , b/ 2 , m);
return mul * mul % m;
}
}
In the above code, the condition if(b %2 == 1) can be replaced by if(b& 1). This is because b& 1 performs a bit AND operation to determine whether the last bit of b is 1, so when b is odd, b&1 returns 1, and the if condition is satisfied. In this way , the write execution speed will be faster.
Also note that when b%2==0 do not return binaryPow (a, b/2, m) binaryPow (a, b/2, m) directly, but should calculate a single binaryPow (a, b/2, m ) and then take it up again. This is because the former calls two binaryPow functions each time , resulting in a complexity of O(2^log(b)) = O(b). For example , when binaryPow (8) is sought, it will become binaryPow (4) binaryPow (4), and the two binaryPow (4) will each become binaryPow (2) binaryPow (2), so it is necessary to find binaryPow ( 2) four times ); and each biaryPow (2) will become binaryPow (1) binaryPow (1), so in the end, binaryPow (1) needs to be calculated eight times .
In addition, for different topics, there may be two details to pay attention to:
① If a may be greater than or equal to m at the beginning, then you need to let a modulo m before entering the function.
②If m is 1, it can be directly judged as 0 outside the function , and there is no need to enter the function to calculate (because any positive integer modulo 1 must be equal to 0).
Next, we will study the iterative writing method of fast power .
For ab, if b is written in binary, then b can be written as the sum of several second powers . For example, the binary of 13 is 1101, so bit 3, bit 2, and bit 0 are all 1, then you can get 13=23+22 +20=8+4+1, so a13=a8+4+1 =a8 a4 a0.
Through the above derivation, we find that a13 can be expressed as the product of a8, a4, and a0. It is easy to imagine that through the same derivation, we can express any ab as the product of several items in a2k,...,a8,a4,a2,a1, where if the bit i of the binary of b is 1, then the item a2i is Selected. So you can get the general idea of calculating ab: let i enumerate each bit of the binary of b from 0 to k, if the current bit is 1, then accumulate a2i. Note that the previous item of the sequence a2k, ... , a8, a4, a2, a1 is always equal to the square of the next item, so you can do the following when implementing:
① Initially set ans equal to 1, which is used to store the accumulated results.
② Determine whether the binary end of b is 1 (that is, to determine whether b & 1 is 1, which can also be understood as judging whether b is an odd number), and if so, multiply ans by the value of a.
③ Make a square and shift b to the right by one place (it can also be understood as dividing b by 2).
④ As long as b is greater than 0, return ② .
Let's write the above pseudocode as follows, which is the iterative writing method of fast power :
//c/ c++
typedef long long LL;
//Seek a^b % m , iterative writing
LL binaryPow ( LL a , LL b , LL m)
{
LL ans = 1 ;
while ( b > 0 )
{
if ( b & 1 )
{ //If the binary end of b is 1 (can also be written as if(b % 2))
ans = ans * a % m; //Let ans accumulate on a
}
a = a * a % m; //Square a
b >>= 1 ; // shift the binary of b right by 1 bit, i.e. b = b >> 1 or b = b / 2
}
return ans ;
}
#python
def qpow ( a,b ,mod ):
ret = 1
while b:
if(b&1):
ret = ret*a % mod
a = a*a % mod
b>>=1
return ret