Math.pow() 함수에 대한 정리

알고리즘 문제를 푸는 도중, Math.pow() 함수에 대해 깊이 생각해보지 못한 부분을 발견하여 이를 정리해보려 합니다.

---

1. Math.pow()란?

Math.pow(base, exponent)는 JavaScript에서 제공하는 내장 함수로, 특정 숫자 base를 exponent 거듭제곱한 값을 반환합니다.
MDN 공식 문서

예시:

console.log(Math.pow(2, 3)); // 8
console.log(Math.pow(5, -1)); // 0.2
console.log(Math.pow(10, 0)); // 1

---

2. Math.pow()를 직접 구현해본다면?

이 함수를 직접 구현한다면 어떻게 해야 할까요?
단순한 방법으로는 다음과 같이 반복문을 사용하는 방식이 떠오릅니다.

function naivePow(base: number, exponent: number): number {
  let result = 1;
  let exp = exponent;
  
  while (exp > 0) {
    result *= base;
    exp--;
  }
  
  return result;
}

문제점

위와 같은 방식은 간단하지만, 다음과 같은 한계가 존재합니다:

1. 시간 복잡도: exponent의 크기에 비례하여 반복 횟수가 증가하므로, 시간 복잡도가 O(n)입니다.
2. 성능: exponent가 큰 경우, 특히 알고리즘 문제에서 다루는 큰 수 연산에서는 비효율적입니다.

---

3. 더 효율적인 방법은 없을까? - 이진 거듭제곱

Math.pow()의 연산을 최적화하려면 이진 거듭제곱(Binary Exponentiation) 알고리즘을 사용할 수 있습니다.
이 방법을 사용하면 시간 복잡도를 O(log n)으로 줄일 수 있습니다.

이진 거듭제곱의 아이디어

1. exponent를 이진수로 표현하면, 거듭제곱 계산을 반복문이 아닌 분할 정복 방식으로 처리할 수 있습니다.
2. exponent가 짝수인지, 홀수인지에 따라 다음과 같이 나누어 처리합니다:
   • 짝수(exponent % 2 === 0):
     $base^{exponent} = (base^{exponent/2})^2$
   • 홀수(exponent % 2 === 1):
     $base^{exponent} = base \times base^{exponent-1}$

예시: 313 계산

풀이 과정

1. ( 13 )을 이진수로 표현하면 ( 1101 ) (2진법)입니다.
   이는

   $3^{13} = 3^{8} \times 3^{4} \times 3^{1}$

   로 표현할 수 있습니다.

2. 이진 거듭제곱 과정

   • 초기값: result = 1, base = 3, exponent = 13
   • Step 1: exponent % 2 === 1
     • 홀수이므로
       result = result * base
       result = 3,
       base = 3^2 = 9,
       exponent = 6
   • Step 2: exponent % 2 === 0
     • 짝수이므로
       base = base^2
       result = 3,
       base = 9^2 = 81,
       exponent = 3
   • Step 3: exponent % 2 === 1
     • 홀수이므로 result = result \times base )
       result = 3 * 81 = 243 ,
       base = 81^2 = 6561,
       exponent = 1
   • Step 4: exponent % 2 === 1
     • 결과
       result = 243 * 6561 = 1594323,
       base = 6561^2,
       exponent = 0

3. 최종 결과: result = 1594323

구현

function binaryExponentiation(base: number, exponent: number): number {
  let result = 1;
  let currentBase = base;
  let exp = exponent;

  while (exp > 0) {
    // 홀수인 경우
    if (exp % 2 === 1) {
      result *= currentBase;
    }
    // base^exponent/2 계산
    currentBase *= currentBase;
    exp = Math.floor(exp / 2);
  }

  return result;
}

시간 복잡도

• 이진 거듭제곱의 반복 횟수는 exponent의 비트 수에 비례합니다.
• 따라서 시간 복잡도는 O(log n)입니다.

---

4. 확장: Modular Exponentiation (모듈러 연산과 결합)

알고리즘 문제에서는 보통 결과를 특정 수로 나눈 나머지 값을 구하는 모듈러 연산이 필요합니다.
이진 거듭제곱은 모듈러 연산과도 잘 결합할 수 있습니다.

구현

function modularExponentiation(base: number, exponent: number, mod: number): number {
  let result = 1;
  let currentBase = base % mod; // base를 미리 mod로 나눔
  let exp = exponent;

  while (exp > 0) {
    if (exp % 2 === 1) {
      result = (result * currentBase) % mod;
    }
    currentBase = (currentBase * currentBase) % mod;
    exp = Math.floor(exp / 2);
  }

  return result;
}

---

6. 정리

• 단순하게 사용했던 Math.pow() 이진 거듭제곱을 이해하고 활용하면 도움이 될것같습니다.
• 알고리즘 문제에서는 모듈러 연산과 결합하여 더욱 효율적으로 사용할 수 있습니다.
• 항상 이진 거듭제곱이 효율적인것은 아니며 Addition-Chain Exponentiation이란 지수 연산을 통해 특정 케이스에 대해서는 더 적은 연산 횟수로도 가능하다고 한다.

---

참고 자료

• MDN Math.pow
• 이진 거듭제곱 알고리즘 (위키백과)