Блог пользователя sonu007

Modular_arithmetic
Автор sonu007, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить