Booth 알고리즘

부호 있는 곱셈에 대한 보다 세련된 접근 방법은 Booth 알고리즘(Booth`s algorithm)이라고 불린다. 이 알고리즘은 덧셈과 뺄셈을 이용해서 곱셈을 계산하는 방법이 여러 가지 있다는 관찰에서 시작된다. 에 또는 에 을 곱하는 경우를 생각해 보자.

×
+ shift (0 in multiplier)
+ add (1 in multiplier)
+ add (1 in multiplier)
+ shift (0 in multiplier)
Booth는 덧셈과 뺄셈이 가능한 ALU는 똑같은 결과를 한 가지 이상의 방법으로 구할 수 있다는 것에 주목하였다. 예를 들어서,
또는
이기 때문에 승수에 일련의 1로 이루어진 열이 존재할 경우, 첫 번째 1을 만났을 때 빼고, 마지막 1을 만난 직후 더하는 것으로 바꿀 수 있다. 예를 들어,

×
+ shift (0 in multiplier)
- sub (first 1 in multiplier)
+ shift (middle of string of ls)
+ add (prior step had last 1)