pow(a, n) for n is large

def pow(a, n):

k = 1

a_pow_k = a

a_pow_n = 1

while n:

if k & n:

a_pow_n *= a_pow_k

n -= k

a_pow_k = a_pow_k ** 2

k *= 2

return a_pow_n

aⁿ = a^klmno = a^k0000 a^l000 a^m00 aⁿ⁰ a^o 

위 식에서 klmno 는 n의 2진수 표현. 즉, a^2k 들의 곱만으로 aⁿ 을 쪼갤 수 있고,

a^2k 는 a^2k-1의 제곱이므로, 위 함수와 같이 빠르게 aⁿ 을 구할 수 있다.

위 함수는 변형하여 aⁿ의 나머지 연산 값을 구할 때 유용할 수 있겠다.