A tutorial on Fast Modulo Multiplication (Exponential Squaring)

suraj Unacademy Subscription
, ,
21

You can make it even faster by using bitwise operators to check for parity (n&1 instead of n%2==1) and to divide by two (n=n>>1 instead of n=n/2). :slight_smile:

22

This is truly a great psot thanks for sharing. Excellent and decent post. I found this much informative, as to what I was exactly searching for. Thanks for such post and please keep it up.

23

https://www.youtube.com/watch?v=wAyrtLAeWvI&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=7 great explanation by mycodeschool…

24

can somebody explain this solution

25

@kuruma
One thing I would like to add … your code fails when the exp = 0 , Output should be 1 but your code doesn’t produce any output . Adding and if statement will do the job . :slight_smile:

26

thanks @kurma that’s really helpfull

27

in the wikipedia solution can’t we directly return base1%1000000007

28

Hey, I don’t clearly understand the implementation. As per the formula above for the fast-exponentiation method given on wikipedia, why don’t we write it’s implementation as given below.

long long fast_exp_1(long long x, int n)
{
	if(n==1)
		return x;
	if(!(n&1))
		return fast_exp_1(pow(x,2),n/2) % MOD;
	else
		return (x*fast_exp_1(pow(x,2),(n-1)/2)) % MOD;
}

Your help is really appreciated. Thanks in advance :slight_smile:

29

pow function is costly. It can potentially increase runtime by a factor of at least 5. I got TLE on using pow(2,x) when T.L. was 2 seconds, but replacing it with 1<<x got AC in 0.2 secs.

1 Like