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)를 구성해야합니다. –

print 서술문을 추가했지만 도움이되지 않아 모듈 식 지수 또는 C++ 자체의 아이디어로 이해할 수 없다고 생각하기 시작했습니다. – Qbik

작동하지 않는 간단한 테스트 케이스를 찾아야합니다. print 문을 추가하여 매 반복마다 매 변수마다 값을 추적하고 수동 계산과 비교하십시오. 불일치가 생기 자마자 버그를 발견했습니다. –

이 함수 mulmod1에 대한 입력을 소독합니다! unsigned은 9688563*9688563을 보유 할 수 없습니다. 이 작업을 제대로 수행하려면 모듈화 된 지수 연산을 올바르게 수행하기 위해 modulus * modulus (물론 입력 번호)을 저장할 수있는 데이터 형식 만 있으면됩니다.

출처

2013-03-03 12:55:19 us2012

unsigned long long 또한 더 큰 숫자에 적합한 다른 가상 코드를 시도해야합니다. – Qbik

@Qbik 명확하지 않은 경우, 계산을하기 전에'base = base % modulus'라고 제안했습니다. .. – us2012

방금 추가 한 무언가가 여전히 잘못되었습니다 mulmod1 (9688563,45896, 71)은 30 대신 20을 제공합니다. – Qbik

C++의 모듈러 지수화

답변

관련 문제