이진수를 이용하여 O(log n)으로 거듭 제곱 빠르게 계산하기

일단 코드부터 살펴 보자

def answer(a, b):
    ret = 1
    while b:
        if b % 2 == 1:
            ret = ret * a
        a =  a * a
        b //= 2

    return ret

ex) 3의 13승을 이진수를 이용하여 구해 보자

13은 2진수로 1101(2)로 변환된다.

즉, 3의 1101(2) 승을 구하는 것이다.

3^1101(2) = ( 0 or 1 ) 3^1 x ( 0 or 1 )3^10(2) x( 0 or 1 ) 3^100(2) x ( 0 or 1 )3^1000(2)

( 지수의 자릿수만큼의 항이 만들어 진다.)

10(2)는 1(2)의 2승이고, 100(2)는 10(2)의 2승, 1000(2)은 100(2)의 2승이다.

4번의 반복을 통해 1101(2)의 각 자릿수\( 0 or 1)를 추출을 하여,

만약 

1] 나머지가 0 : 1101(2)의 다음 자릿수를 다시 구함

2 ] 나머지가 1 : 만약 1101(2)의 3번째 자릿수가 1이였을 경우,  3 ^ 100(2) == 3^4 를 곱하면 된다.