Почему pow (x, y, z) эффективнее, чем (x^y)% z?

Question

Во многих языках программирования первый из них быстрее. Почему это?

Answer 1

pow(x,y,z) обычно реализуется как это (Java):

int pow(int x, int y, int mod) { 
    long res = 1, p = x; 
    while (y > 0) { 
     if (y%2 == 1) { 
      res = (res*p)%mod; 
     } 
     p = (p*p)%mod; 
     y /= 2; 
    } 
    return (int)res; 
} 

имеет O (журнал у) сложность, которая намного лучше по сравнению с O (у) в случае прямой реализации с y умножений.

Второе преимущество заключается в том, что некоторые языки будут использовать длинную арифметику, если результат операции превышает размер машинного слова (32 или 64 бит). Таким образом, в случае простой реализации потенциально огромное количество x^y будет вычислено сначала, и только тогда будет выполнено по модулю z.