A booth's example

booths.md

#Booth's algorithm

base 10

-13 * 9 = -117

binary

 -13 = 10011
   9 = 01001 
-117 = 11100 01011

multiplicand = 10011
multiplier = 01001
product = 11100 01011

Working through Booth's

Let A = 01001 (the multiplier)
Let B = 10011 (the multiplicand)
-B = 01101  (compliment of B)

Note: instead of subtracting the multiplicand (B) in the appopriate steps below, I will be adding the compliment of the multiplicand (-B). This is a personal preference as I don't like binary subtraction

Iteration   Step    Product         L   Desc
0           0       00000 01001     0   init
1           1       01101 01001     0   Subtract (add -B to leading 5 bits) 00000 + 01101 = 01101
            2       00110 10100     1   logical shift right
2           1       11001 10100     1   Add (add B to leading 5 bits) 00110 + 10011 = 11001 
            2       11100 11010     0   logical shift right
3           1       11100 11010     0   No Op
            2       11110 01101     0   logical shift right
4           1       01011 01101     0   Subtract (add -B to leading 5 bits) 11110 + 01101 = 101011 (drop most sig bit)
            2       00101 10110     1   logical shift right
5           1       11000 10110     1   Add (add B to leading 5 bits) 00101 + 10011 = 11000 
            2       11100 01011     0   logical shift right
            

Done!