수학 알고리즘 - 거듭제곱 알고리즘(반복문, 분할정복)

거듭 제곱이란

거듭 제곱은 한 수를 다른 수의 거듭제곱으로 나타내는 것을 말합니다. 2의 3승은 2 * 2 * 2 = 8입니다.

 

반복문을 이용한 거듭 제곱 코드 예시

function power(n, m) {
 let result = 1
 for(let i = 1, i <= m; i++) {
  result *= n
 }
 return result
}

n을 m번만큼 곱합니다.

 

분할 정복을 이용한 재귀 거듭 제곱 코드 예시

function power(n, m) {
 function fastPower(n, m, r) {
  if(m === 0) return r
  if(m % 2) return r *= n
  return fastPower(n*n, m >> 1, r)
 }
 return fastPower(n, m, 1)
}

숫자와 지수를 받아서 거듭제곱하는 함수입니다.

재귀를 통해 r에 현재 계산 결과를 가지고 있습니다.

만약 지수가 0이면 현재 계산 결과를 반환합니다.

지수가 홀수이면 숫자를 한번더 곱합니다.

2^5이면 2^2 * 2^2 * 2이 계산이기때문에 홀수일 때 숫자를 더 곱해야됩니다.

지수가 짝수면 지수는 반으로 줄이고 숫자를 제곱하여 넘겨줍니다.

2^4 = 2^2 * 2^2

2^2 = 2^1 * 2^1

2^1 = 2^0 * 2^0 * 2

이러면 지수 연산을 효율적으로 하는 분할 정복 재귀 알고리즘입니다.

 

반복문을 이용한 재귀 거듭 제곱 코드 예시

function fastpow2(a, b) {
    let result = 1
    while(b > 0) {
        if(b % 2) result *= a
        a *= a
        b = parseInt(b / 2)        
    }
    return result
}

위에 재귀 분할 정복을 반복문으로 바꿨습니다.