In competitive programming, traditional way to finding power may not work sometimes.
By traditional way I mean if we have to find 2^10 (just as an example).
Or else simply by using library function after including math.h (in C) we can do it by pow(2,10)
Well, but this doesn't help us anymore when it comes to finding base to the power (base^power) where power could be anything in the range 0 to 1000000 or even greater value, same goes for base
Whilst you may think it impractical but in competitive programming questions ask us find Modulus of the answer by any prime number such as 1000000007, just to make sure answer remains in range of int data type.
i.e. pow(2,100)%1000000007 = 976371285
Lets come to the point and discuss what you have come for :)
Fast Algorithm:
result = 1
If power is odd:
result = result*value
value = value*value
power = power/2
Yeah, I know, above algorithm more looks like a code & was nothing but a bouncer. ;)
Lets discuss an example of what exactly we are doing here. Same example 2^10.
We know,
2^10
= (2*2) * (2*2) * (2*2) * (2*2) * (2*2)
= 4^5 // here power has become odd, so lets take out one 4 out of five 4's & multiply it with 'result' & store back in 'result' & hence we are left with four 4's
So result = 4 and we are left with 4^4
4^4
= (4*4) * (4*4)
= 16^2 // since power is even no need to mess up our result variable
16^2
= 256^1 // here power has become odd, so lets take out one 256 & multiply it with 'result' & store back in 'result' hence we are left with zero 256's
Viola, power became zero. Its the end. Now our result contains what we want.
Following is C/C++ implementation of fast powering algorithm.
Line #8: (power&1) is a better/faster way to check if a number if odd or not
Line #14: I commented it out, but that too is an alternative of Line #13
Following is Python implementation of the Fast/Quick Power Algorithm.
Got a burning question you might wanna get answered? Ask it in the comments or mail me or leave a message on my Facebook Page
Happy Coding.
By traditional way I mean if we have to find 2^10 (just as an example).
Or else simply by using library function after including math.h (in C) we can do it by pow(2,10)
Well, but this doesn't help us anymore when it comes to finding base to the power (base^power) where power could be anything in the range 0 to 1000000 or even greater value, same goes for base
Whilst you may think it impractical but in competitive programming questions ask us find Modulus of the answer by any prime number such as 1000000007, just to make sure answer remains in range of int data type.
i.e. pow(2,100)%1000000007 = 976371285
Lets come to the point and discuss what you have come for :)
Fast Algorithm:
result = 1
If power is odd:
result = result*value
value = value*value
power = power/2
Yeah, I know, above algorithm more looks like a code & was nothing but a bouncer. ;)
Lets discuss an example of what exactly we are doing here. Same example 2^10.
We know,
2^10
= (2*2) * (2*2) * (2*2) * (2*2) * (2*2)
= 4^5 // here power has become odd, so lets take out one 4 out of five 4's & multiply it with 'result' & store back in 'result' & hence we are left with four 4's
So result = 4 and we are left with 4^4
4^4
= (4*4) * (4*4)
= 16^2 // since power is even no need to mess up our result variable
16^2
= 256^1 // here power has become odd, so lets take out one 256 & multiply it with 'result' & store back in 'result' hence we are left with zero 256's
Viola, power became zero. Its the end. Now our result contains what we want.
Following is C/C++ implementation of fast powering algorithm.
Line #8: (power&1) is a better/faster way to check if a number if odd or not
Line #14: I commented it out, but that too is an alternative of Line #13
Following is Python implementation of the Fast/Quick Power Algorithm.
Got a burning question you might wanna get answered? Ask it in the comments or mail me or leave a message on my Facebook Page
Happy Coding.
