Arithmetic for Computers(1)

Multiplication

Shift-Add Algorithm

이건 시프트와 덧셈을 반복하는 방식이다

곱셉도 결국 덧셈의 반복이기때문에, 곱하는 쪽의 각 비트를 하나씩 확인하면서 1이면 더하고, 0이면 그냥 시프트만 한다.

과정

1. Multiplier의 LSB가 1이면 Multiplicand를 Product에 더한다.
2. Multiplicand를 왼쪽 시프트, Multiplier를 오른쪽 시프트한다
3. 이걸 비트 수만큼 반복한다.

이 방식은 간단하지만 매 단계가 순차적으로 느리다. ⇒ 비트 수만큼 사이클이 필요함

Optimized Multiplier

이제는 모든 부분 곱을 동시에 계산하고, 병렬로 더하는 구조를 쓴다.

앞에서는 자세히보면 Product 의 상위 4비트는 놀고 있고, 하위 4비트는 초기에는 0000이다.

그래서 하위 4비트에 기존의 Multiplier를 넣어주고, 계산 결과를 상위 4비트에 저장한다.

하위 4비트 중에서 LSB를 확인하고 1이면 Multiplicand의 값을 Product의 상위 4비트에 더한다.

다음으로는 Product를 오른쪽으로 시프트한다.

이 과정을 끝까지 반복하면 마지막엔 Product에 계산 결과만 남게 된다.

• Add와 Shift를 병렬로 수행한다. → 각 단계에서 하나당 partial-product를 추가한다.
• 그래서 한 사이클당 한 번의 덧셈 정도로 속도가 개선된다

Division

Original

과정

1. Remainder ← 0
2. Divident의 최상위 비트를 Remainder로 가져온다.
3. Divisor는 그대로 유지
4. Remainder ← Remainder - Divisor
5. 결과가 음수면?
6. 결과가 양수면?
7. Divisor를 오른쪽으로 시프트
8. 이걸 피연산자 비트 수만큼 반복

Optimized Divisor

곱셉기와 비슷하게 한 사이클당 한 번의 Partial remainder 연산만 수행하게 한다.

과정은 Multiplier 했을 때랑 비슷하다.

1. 먼저 Dividend를 Remainder에 저장한다.
2. 실제 내가 나눗셈을 하는 부분은 Remainder의 상위 4비트다.
3. 그래서 처음에 Remainder를 왼쪽으로 시프트해서 비트를 하나 가져온다. 처음에는 0이니까.
4. Remainder(상위 4비트)와 Divisor의 차를 생각해서 음수냐 양수냐에 따라 각각 Quotient를 0이나 1로 채운다.
5. 이 과정을 끝까지 반복하면 Remainder의 상위 4비트는 최종 Remainder고, 하위 4비트는 Quitient가 된다.