這個函數爲什麼有效計算模塊化pow值？

我已經看到了SRM 573's solution here:這個函數爲什麼有效計算模塊化pow值？

long modPow(long x, long y) 
{ 
    //Caculates x raised to the y-power modulo MOD 
    //in O(log(y)) time by using repeated squaring 
    long r = 1; 
    while(y > 0){ 
     if((y&1) != 0) { 
      r = (r * x) % MOD; 
     } 
     x = (x * x)%MOD; 
     y >>= 1; 
    } 
    return r; 
}

這個功能，但我對這個功能感到困惑於計算x^y%MOD模塊化值;
爲什麼x = (x * x)%MOD;需要在函數中？
這對我沒有意義。

來源

2013-03-27 Al2O3

tl; dr：這是一個優化。

想象一下，x是2，MOD是3.請注意，唯一的x用於將r乘以x。

現在想象我們平方x。 x * x = 4。現在，r * 4％3將等於1,2,3,4,5 ......對於r = 1,2,3,4,5 ......哦！它與x是1相同。實際上，如果將x設置爲x * x％3而不是x * x，則會得到相同的結果。

但是下一步呢？ 4 * 4 = 16，％3 = 1。1 * 1 = 1，％3也= 1。所以，無論我們提前還是延遲或從不改變操作，我們都會陷入相同的殘差。

來源

2013-03-27 02:32:17 Patashu

在每次通過下面顯示的循環時，低位將從y移出，其中y作爲基址x將被提升到的指數開始。

long r = 1; 
while(y > 0){ 
    if((y&1) != 0) { 
     r = (r * x) % MOD; 
    } 
    x = (x * x)%MOD; 
    y >>= 1; 
}

例如，如果y = 0b1101，或13小數，然後xʸ = x¹³ = x¹⁺⁴⁺⁸ = x·x⁴·x⁸和if((y&1) != 0) r = (r * x) % MOD部分將由x在第一，第三和第四遍相乘r，當x的電流值是第一，第四，和原始值的八次方。

請注意，因爲(a·b) mod p ≡ ((a mod p)·(b mod p)) mod p,mod函數可以在每次乘法之後應用。經常應用它可以最大限度地減少乘法所需的位數。

來源

2013-03-27 03:34:53

闡述了幾分@ jwpat7的回答，讓我們想想爲什麼

(x % MOD)*(x % MOD) ≡ (x*x) % MOD。

我們總是可以寫x作爲x = n*MOD + r一些土黃n和r與r < MOD（如果還x < MOD暗示x = r和n = 0）。

現在，我們總是得到x % MOD = (n*MOD + r) % MOD = r，因此我們得到

(x % MOD)*(x % MOD) = r * r。

在另一方面，考慮什麼(x*x) % MOD計算結果爲：

x*x = (n*MOD + r)*(n*MOD +r) = n*n*MOD*MOD + 2*n*r*MOD + r*r，因此我們得到(x*x) % MOD = (n*n*MOD*MOD + 2*n*r*MOD + r*r) % MOD = r*r

這就是爲什麼Patashu說，這不要緊，無論您提前或延後應用模運算符，因爲剩下的r就是與模操作實際相關的所有內容，也是唯一進行下一次迭代的事情。

來源

2013-03-27 03:44:41

暫時忘掉模塊化部分，然後問自己：「我怎樣纔能有效地計算n個正整數的x^n？」可以用一個乘法計算x^2：x * x。你可以用兩次乘法計算x^3：x^3 = x * x^2。您可以用兩次乘法計算x^4：x^4 = x^2^2 = x^2 * x^2。你可以計算出一般的X^N與此遞歸：

For even n = 2*m, x^n = (x^2)^m. 

For odd n = 2*m + 1, x^n = x * (x^m)^2.

所以，我們得到的x^10：

x^10 = (x^2)^5 
    = x^2 * (x^4)*2

計算x^2，X^4，X^8，X^10，進行4次乘法運算。

請注意，這是一個很好的通用方法，但不能保證是最有效的。例如，嘗試x^15。這個方法給你x *（x^2）^ 7 = x * x^2 *（x^2）^ 6 = x * x^2 ^（x^4）^ 3 = x^x^2 * x^4 *（x^4）^ 2。您計算x^2，x^4，x^8，然後計算6次乘法的x * x^2 * x^4 * x^8。更快的是

y = x^3 = x * x^2, 2 multiplications. 
x^15 = y^5 = y * (y^2)^2, 3 more multiplications, 
This is a total of 5 multiplications.

事實上，對於一個指數n，定義一個加法鏈如從1開始，並在n，其中列表中的每個數爲2件前面的數之和在序列中結束的數字序列（你可以重複）。

15的算法給出

1，2，3，6，7，14，15，

較短的一個是

1，2，3，6，12，15

事實證明，在計算上很難找到以目標數字結尾的最短加法鏈。

來源

2013-03-27 04:22:12

這個函數爲什麼有效計算模塊化pow值？

回答

相關問題