지난 「기본 자료형 어쩌고」 글에서 산술 연산자 없이 곱셈을 구현했었는데, 이번에는 Booth's algorithm을 이용해 새롭게 구현해보았다.
int add(int x, int y) {
while(y) {
int carry = x & y;
x ^= y;
y = (carry << 1);
}
return x;
}
int booth_s (int x, int y) {
int res = 0, cnt = 0, buff = 0;
while (cnt < 32) {
if((y & 0x01) != buff) {
res = add(res, ((y & 0x01) == 1) ? add(~x, 1) : x);
}
buff = y & 0x01;
y >>= 1; x <<= 1;
cnt = add(cnt, 1);
}
return res;
}buff는 쉬프트 되는 LSB를 저장한다.
📋Booth's algorithm
부스 알고리즘은 컴퓨터 구조를 배울 당시 곱셈 하드웨어를 최적화하는 대안으로 공부했었다. 당시에도 간단하면서도 효율적인 알고리즘이라 생각했어서 기억에 잘 남았다.
부스 알고리즘의 기본 원리는 다음과 같다.
(다음 수들은 모두 이진수이다.)
어떤 변수 x가 주어졌다고 하자.
x * 0111 을 계산할 때, 무식하게 접근하면, 1씩 빼가면서 0이 될 때까지 x를 더하는 방식이 있겠다. 이런 방법은 비트가 N개 일때, N에 대한 밑이 2인 지수함수 형태의 성능을 보인다.
0111의 최하위 비트를 계산하고, x를 결과에 더한 뒤, 0111을 오른쪽 쉬프트 하면서 함께 x를 왼쪽 쉬프트하는 과정을 반복하는 방법도 있겠다. 이 경우 set된 비트의 개수만큼 덧셈 연산이 이루어질 것이다.
부스 알고리즘은 x * 0111이란 식을 재구성한다.
x * 0111 = x * 1000 - x * 0001 = x * (1000 - 0001)
기존의 알고리즘에 의하면 총 3번의 덧셈이 수행되어야 하지만, 부스알고리즘은 2번의 연산으로 곱셈을 구현하게 된다.
이런 연산은 특히 임의의 긴 비트열인 경우 효과적이다.
예시로 01111111111111111111111111111111이 x과 곱해질 때, 31번의 덧셈과 쉬프트가 수행되는 것과 대조적으로 부스알고리즘은 2번의 덧셈으로 결과를 계산한다.
부스 알고리즘의 시작은 우선 buffer (이후 x * y에서 y의 최하위를 저장하는 FF)에 0이 들어있다고 가정한다.
이렇게 하는 이유는 00001 * x를 빼주는 것을 보장하기 위해서이다.
진리표는 다음과 같다.
y & 0x01 | buffer | operation
0 | 0 | none
0 | 1 | add
1 | 0 | subtract
1 | 1 | none
부스 알고리즘이 이런 단순한 연산으로 곱셈을 구현 가능한 이유는 아무리 복잡한 비트열이라도 분해하여 나타낼 수 있기 때문이다.
ex)
011011001101111 은
100000000000000 - 001000000000000 + 000100000000000 - 000001000000000 + 000000010000000 - 000000000100000 + 000000000010000 - 000000000000001 로 분해된다.
이 예시가 시사하는 바는 최하위 비트부터 부스 알고리즘에 의한 연산을 수행해나갈 경우 전체 비트를 1번만 훑어도 된다는 점이다.
특히 10000 - 00001은 최초에 1번 x를 빼줘야 하는데, 진리표에 따라 subtract를 수행하기 위해선 y 최하위 비트가 1, buffer가 0이어야 한다. 따라서 처음에 buffer에 0을 저장한다.
