sonu007's blog

Modular_arithmetic
By sonu007, history, 8 years ago, In English

int modpow(int x, int n, int m) { if (n == 0) return 1%m; int u = modpow(x,n/2,m); u = (u*u)%m; if (n%2 == 1) u = (u*x)%m; return u; }

Please explain modpow(x, n/2, m) call again and again when below its code execute.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To understand how this works you need to know this following formula:

(A^n) % M = [ { (A^(n/2)) % M } * { (A^(n/2)) % M } ] % M [when n is even]

if n is odd then we can always write that

(A^n) % M = [ (A % M) * {(A^(n-1)) % M} ] % M [and now n-1 is even so we can apply the first formula]

This is the fundamental of binomial exponentiation. If you are required to calculate (A^N) % M in O(log N) time then this is the approach you should follow. If you still can't understand how that code works by calling itself in itself then I would suggest that you learn about recursions.

For more info: https://e-maxx-eng.appspot.com/algebra/binary-exp.html

→ Reply