Booth's Algorithm is a pretty fast algorithm for multipling signed binary numbers.
Normal method for multiplying:
7 * 3 = 0111 * 0011
Just as you would multiply multi-digit numbers:
0111 * 0011
-----------
0000000
+    000000
+     01110
+      0111
-----------
10101 = 21

Obviously this method is very time-consuming, as several XORs and ANDs are used.
Booths alogritm is not so wasy to understand, but uses less operations: You use 4 registers A,M, Q, c. A, M, Q are as wide as the numbers (Q and M contain the numbers which will be multiplied), but c is only 1 bit wide. What one does in each step is depends on the values of the LSB of Q and c:

LSB(Q) c
0      0   right-shift
0      1   add M to A and right-shift
1      0   substract M from A and right shift
1      1   right-shift

This is done n times, where n is the width of Q and M. Right-shifting is done, using A, Q and c as one register, while the new MSB of A is equal to the old MSB of A:
A = 0000 Q = 0010 c=0 = 000000100 => 000000010
A = 1000 Q = 0010 c=0 = 100000100 => 110000010

Now an example for the algorithm:
7 * 3 = 0111 * 0011
M = 0111
A = 0000
Q = 0011
c = 0

M     A     Q    C    Operation      #
0111  0000  0011  0
0111  1001  0011  0    substract   \  1
0111  1100  1001  1    right shift /
0111  1110  0100  1    right shift    2
0111  0101  0100  1    add         \  3
0111  0010  1010  0    right shift /
0110  0001  0101  0    right shift    4
The result is in A and Q: 10101 = 21.
The main idea behind this algorithm is, that 11100 = 11111 - 11. So if you come to the beginning of a string of 1s in Q, you substract M from A. If you come to the end, you add it again (but more left, as you shifted right).

Example of the Booth's Algorithm in MIPS assembler

.text 0x400000
main:
li \$v0, 5
syscall
move \$s0, \$v0
li \$v0, 5
syscall
andi \$s1, \$v0, 0x0000ffff
sll \$s0, \$s0, 16                    # into Upper-Halfword (for addition)
li \$s4,0                            # saving the last bit
li \$s5,16                           # counter
loop:
andi \$s3, \$s1, 1                    # \$s3 = LSB(\$s1)
beq \$s3, \$s4, endloop               # 00 or 11 -> cont
beq \$s3, \$zero, runend              # 01 -> runend
sub \$s1, \$s1, \$s0                   # beginning of a run
j endloop
runend:
endloop:
sra \$s1, \$s1, 1                     # arithmetic right shift
move \$s4, \$s3
bne \$s5, \$zero, loop

li \$v0, 1
move \$a0, \$s1
syscall
end:
li \$v0, 10
syscall

Log in or register to write something here or to contact authors.