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:
add $s1, $s1, $s0
endloop:
sra $s1, $s1, 1 # arithmetic right shift
addi $s5, -1
move $s4, $s3
bne $s5, $zero, loop
li $v0, 1
move $a0, $s1
syscall
end:
li $v0, 10
syscall