알고리즘power

function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

  if (exponent % 2 === 1) return (base * result) % 94906249;
  else return result;
}

power(2,9) 함수를 호출하면 다음과 같이 작동한다.

1. power(2, 9) 함수가 호출되면, exponent 값인 9가 0이 아니므로 2단계로 이동한다.
2. exponent를 2로 나눈 몫인 4이 half 변수에 저장된다. 그리고 power(2, 4) 함수를 호출하여 temp에 결과값인 16이 저장된다.
3. temp를 두 번 곱한 결과인 256이 result에 저장된다. 그러나 result 값이 너무 커져서, 94906249로 나눈 나머지인 256으로 저장된다.
4. exponent가 홀수이므로, base(2)와 result(256)를 곱한 결과인 512가 반환된다.  이 값도 94906249로 나눈 나머지인 512으로 저장된다.

따라서 power(2,9) 함수는 256 대신 256으로 나눈 나머지값인 256으로 저장하여, overflow 문제를 해결하고 결과값인 512를 반환한다.

 

power(2,9) 함수에서 power(2,4) 함수가 호출되는 이유는 분할 정복 알고리즘을 이용하기 위해서다,

power(2,9) 함수는 exponent 값이 0이 아니므로, exponent를 2로 나눈 몫인 4를 half 변수에 저장한 후 power(2, 4) 함수를 호출한다.

 

power(2, 4) 함수가 호출되면, exponent 값인 4가 0이 아니므로 power(2,2) 함수를 호출한다.

이어서 power(2,2) 함수도 power(2,1) 함수를 호출하고, power(2,1) 함수는 power(2,0) 함수를 호출한다

power(2,0) 함수에서는 1을 반환하여 함수 호출 스택이 역순으로 반환되면서, power(2,1) 함수에서는 2를 반환하고, power(2,2) 함수에서는 4를 반환한다.

그리고 마지막으로 power(2,4) 함수에서 temp 변수에는 power(2,2) 함수를 호출한 결과인 4가 저장되어 반환된다.

그러면 power(2,9) 함수에서 result 변수에는 temp 변수를 두 번 곱한 결과인 16이 저장되어 반환된다.