A tutorial on Fast Modulo Multiplication (Exponential Squaring)

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

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.

2 Likes

Its Basically reducing the Power which just enlarge the number but reduces the no. of iterations…

You should first try this https://www.codechef.com/problems/FEXP

can u please share the code for this function

Its a standard cpp function. You can google it.

I also made a video on this topic. Fast Modulo Multiplication :slight_smile: .

when i am running this above code in codeblocks it is showing conflicting types of fast_exp i am not getting why this is happening can someone please help.

use powl in place of pow
thank me later :confused: