C++中的模冪運算

我的代碼中模冪運算有點問題，儘管在使用兩個不同的僞代碼時寫三次，我仍然無法發現問題。我已經閱讀了關於SE中C++的模冪運算的其他問題，但這並沒有幫助我。這是我最後的代碼，通過簡單，但較少的最佳方式所寫的，我想：C++中的模冪運算

#include<iostream> 
using namespace std; 

// base^exponent mod modulus 
unsigned mulmod1(unsigned base, unsigned exponent, unsigned modulus) { 
    int result = 1; 
    while(exponent > 0){ 
     if(exponent % 2 == 1) 
      result = (result * base) % modulus; 
     exponent >>= 1; 
     base = (base * base) % modulus; 
    } 
    return result; 
} 

int main(){ 

//9688563^45896 mod 71 = 30 
//12^53 mod 7 = 3 

cout<<mulmod1(9688563,45896 ,71)<<"\n"; //gives 10 instead of 30 
cout<<mulmod1(12,53,7)<<"\n";    //gives correct answer 3 

return 0; 
}

來源

2013-03-03 Qbik

要求人們發現代碼中的錯誤並不是特別有效。您應該使用調試器（或添加打印語句）來隔離問題，然後構造一個[最小測試用例]（http://sscce.org）。 – 2013-03-03 12:53:02

我已經添加了打印語句，但我沒有幫助，現在我開始認爲我不明白模塊冪或C++本身的想法 – Qbik 2013-03-03 12:57:07

您應該找到最簡單的測試用例不起作用，然後添加打印語句以跟蹤每次迭代中每個變量的值，並將其與手動計算進行比較。只要有差異，那麼你已經找到了你的錯誤。 – 2013-03-03 12:57:57

消毒輸入你的函數mulmod1！ unsigned不能容納9688563*9688563。如果你這樣做，你'只'需要一個可以容納modulus * modulus（和你的輸入數字，當然）的數據類型來正確執行模冪運算。

來源

2013-03-03 12:55:19 us2012

unsigned long long也是，所以我必須嘗試另一個僞代碼來適合更大的數字 – Qbik 2013-03-03 12:59:30

@Qbik如果不清楚，我建議您在對它進行任何計算之前先執行'base = base％modulus'。 .. – us2012 2013-03-03 13:00:43

我剛剛加了這個，有些東西還是錯誤的mulmod1（9688563,45896,71）給出了20而不是30 – Qbik 2013-03-03 13:08:56

C++中的模冪運算

回答

相關問題