왜 Recusrsive 모듈러 지수가 반복과 동일하지 않습니까?

Question

는 I 비 재귀 멱승 잉여

typedef long long uii; 
uii modularExponentiation(uii base,uii exponent,uii p) 
{ 
    int result= 1; 
    base = base % p; 
    while(exponent > 0) 
    { 
     if (exponent % 2 == 1) 
      result = (result * base) % p; 
     exponent = exponent >> 1; 
     base = (base * base) % p; 
    } 
    return result; 
} 

구현 한 다른 하나

uii modularExponentiation(uii base,uii exponent,uii p) 
{ 
    if(exponent == 0) 
     return 1; 
    int res= modularExponentiation(base,exponent/2,p); 
    if(exponent%2 == 0) 
     return (res * res)%p; 
    else 
     return ((res*res)*(base%p))%p; 


    return res; 
} 

재귀하지만 두 개의 코드가 올바른 결과를 생성하지 않는다. Wikipedia의 반복 코드는 정확한 결과를 제공합니다. 재귀 버전에서 내가 뭘 잘못했는지, 그리고 그것을 해결하기 위해 무엇을해야합니까?

Answer 1

나는 대신에 int res의 사용이 오버 플로우의 가능성이 있다고 생각합니다. 심지어 더 이상 ((res*res)*base%p)%p 오버플로 발생할 수 있습니다.

향상된 코드 : -

uii modularExponentiation(uii base,uii exponent,uii p) 
{ 
    if(exponent == 0) 
     return 1; 
    uii res= modularExponentiation(base,exponent/2,p); 
    res = (res*res)%p; 
    if(exponent%2 == 0) 
     return res; 
    else 
     return (res*(base%p))%p; 

}