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++中的模幂运算

回答

相关问题