제곱에 의한 지수화 C 구현

Question

C에서 제곱에 의한 지수화 알고리즘을 구현하려고했지만 프로그램에 이상한 동작이 있습니다. 내가 가진 함수를 호출 할 경우

long long fast_power_1(long long base, long long power){ 
    long long result = 1; 
    while (power > 0) 
    { 
     if (power % 2 == 0) 
     { 
      power = power/2; 
      base = base * base; 
     } 
     else 
     { 
      power = power - 1; 
      result = (result*base); 
      power = power/2; 
      base = (base * base); 
     } 
    } 
return result;} 

: 첫째, 여기에 작은 코드 조각입니다

printf("%d\n",fast_power_1(2,100)); 

내가 출력이 976,371,285 같은 것으로 예상하지만, 결과는 0을 그리고 난하지 않습니다 이유를 확실히 이해합니다.

Answer 1

long long은 %lld 형식 지정자를 사용하여 인쇄해야하며 그렇지 않은 경우 정의되지 않은 동작입니다. 또한이 메서드는 이미 power의 큰 값에 대해 오버플로가 있습니다. 왜냐하면 long long cant는 2^100 (현재는 32 또는 64 비트 시스템의 경우 - 128 비트 시스템 일 수 있음)을 유지하기 때문입니다.

현재 코드에서 지수의 값이 너무 크지 않고 printf("%lld",..)을 사용하면 올바른 결과를 얻을 수 있습니다.

아마도 모듈러 연산을 원했을 것입니다. (일반적인 요구 사항에서 그걸 막습니다 - 어떤 큰 프라임을 모듈로, 즉 10^9+7).