A tutorial on Fast Modulo Multiplication (Exponential Squaring)

tutorial
, ,
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