Algorithm Multiply exponents like binary

알고리듬 Multiply exponents like binary를 알아보겠습니다.

​
지수의 성질 중, 곱하기는 더하기가 됩니다.
예를 들어서 x^2 * x^3 = x^5처럼 말이죠.
​
어떤 목표 지수 숫자가 있을 때, 지수의 합이 해당 숫자가 되도록 만들어 봅시다.
​
이때, 이진법을 이용합니다.
이진법은 다음과 같이 0과 1로 구성되어 있습니다. 그리고 자릿수마다 각 숫자가 나타내지는데, 24는 0001 1000으로 표기되고, 10진법으로 변환하면 16 + 8이 됩니다.

이번 시간에서는 x^24를 x^16*x^8로 구하는 알고리듬을 알아봅시다.

7 번째 줄에서 현재 계산하는 위치에 비트가 1 위치하면 tmp를 곱합니다.

11 번째 줄에서 비트를 하나씩 오른쪽으로 옮깁니다. 

​

​

결과는 동일합니다.

직접 손으로 계산해 보면 다음과 같이 됩니다.

0001 1000인데, 이때 tmp는 3^2가 됩니다.

0000 1100인데, 이때 tmp는 3^4가 됩니다.

0000 0110인데, 이때 tmp는 3^8이 됩니다.

0000 0011인데, 이때 tmp는 3^16이 됩니다. x는 3^8이 됩니다.

0000 0001인데, 이때 tmp는 3^32가 됩니다. x는 3^8 * 3^16 = 3^24가 됩니다.

​

​

​

​

끝.

​

카테고리: Algorithm