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
    

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