A tutorial on Fast Modulo Multiplication (Exponential Squaring)

Hey Guys, just a small note who may be having problems using the above functions.
For large values of base and exp you should prefer long long int as data types of base and exponent in fn.
Also, second recursive function is better.
IF you use int data types you may run into run time error, overflow.

Great tutorial … Just a heads-up … the first method caused a RunTime error (SIGSEGV) . I think that it was caused because of the fact that it is a recursive approach and that it takes up too much of memory . The second method is much better … but you should initialize both the exp and base as long long int

1 Like

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:

6 Likes

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.

1 Like

Exponentiation - Calculate Pow(x,n) using recursion - YouTube great explanation by mycodeschool…

2 Likes

@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:

thanks @kurma that’s really helpfull

1 Like

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

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:

Thanks added this to the tutorial :smiley:

very well explained bro…it makes a 10/10 tutorial…:slight_smile:

1 Like

I’m really glad you liked it :smiley:

2 Likes

you are right, fixed it

1 Like

in majority, you don’t use 1 as modulo but yes, you are right :slight_smile:

good post i like it

I am really glad to hear it, @driftking

It’s not visible, can you share it somewhere else? Probably there is overflow in your code…

Hey,i am not getting how your recursion takes %(100000007) at every recursive step to avoid overflow…Can you explain this little bit.I mean to say how recursion work here?Does it calculate a^b and then calculate %(100000007) or it calculates ((a1%(100000007)*(a2%100000007)…)%(100000007).If the answer is latter can you please explain how

actually this tutorial is awesome…I m stucked how can any1 explain so simple…I want to learn programming , algorithm in your guidence please provide me some source to read your blog, tutorial any material produced by you or any1 like you…
thanks for appreaciation…

can somebody explain this solution