为什么我们不需要对 Fast Power 算法中的每个操作数执行模运算？

Question

今天练习了一个谜题"fast power"，用到了一个公式： (a * b) % p = (a % p * b % p) % p 来计算 (a^n)%p，像这样：2^31 % 3 = 2

然而，当我发现答案使用 ((temp * temp) % b * a) % b; 来解决 n 为奇数的情况时，我感到很困惑，比如 2^3

（温度是 (temp * temp) % b * a 递归或 (temp * temp) % b）。

不应该是((temp * temp) % b * a%b) % b吗？

因为按照这个公式，所有的东西都应该%b之前的次数在一起。

Answer 1

Should not it be ((temp * temp) % b * a % b) % b?

没有。对于a，如果事先知道a不会溢出（a小于b），则不必mod。

想法是 modular arithmetic 适用于加法和乘法。 (a + b) % M = (a % M + b % M) % M、(a * b) % M = (a % M * b % M) % M一般是为了避免(a * b)、(a + b)溢出，使值保持在一定范围内。

示例：

const int Mod = 7;
int a = 13;
int b = 12;
int b = b % Mod; // b now contains 5 which is certainly smaller than Mod

int x = (a % Mod * b) % Mod; // you won't need to mod b again if you know beforehand b is smaller than Mod

更新

幂函数的C++实现：

#define MOD 1000000007
// assuming x and n both be positive and initially smaller than Mod
int power(int x, int n) {
    if(n == 0) return x;
    int half = power(x, n / 2) % Mod;
    int ret = (half * half) % Mod; // you didn't need to do (half % Mod * half % Mod) % Mod because you already know half is smaller than Mod and won't overflow. 
                                   // Modulas being performed on the multiplied output, so now ret will be smaller than Mod
    if(n & 1) {
        ret = (ret * x) % Mod; // you didn't need to do (ret % Mod * x % Mod) % Mod
                               // because you already know ret and x is smaller than Mod
    }
    return ret;
}

Mod 是一个昂贵的操作。所以你应该尽可能避免它。

为什么我们不需要对 Fast Power 算法中的每个操作数执行模运算？

Why don't we need to perform modulo operation on every operands in Fast Power algorithm?

c++

math

modular-arithmetic

更新