A tutorial on Fast Modulo Multiplication (Exponential Squaring)

tutorial
, ,
19

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

1 Like
20

I’m really glad you liked it :smiley:

2 Likes
21

you are right, fixed it

1 Like
22

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

23

good post i like it

24

I am really glad to hear it, @driftking

25

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

26

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

27

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…

28

can somebody explain this solution

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.

2 Likes
30

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

31

You should first try this FEXP Problem - CodeChef

32

can u please share the code for this function

33

Its a standard cpp function. You can google it.

34

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

35

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.

36

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

37

Does anyone have a C code for k-ary exponentiation calculation by k as a variable?

38

If anyone is looking for a video explanation of this and more…

Watch this Errichto