이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다. 이것을 빠르게 해 보자! $n$이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ $n$이 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 $3^{60}$을 계산해보자 $3^{60} = 3^{30} \times 3^{30}$ $3^{30} = 3^{15} \times 3..