How to Multiply Using Booth’s Algorithm

In this tutorial, I will discuss how to multiply two numbers using Booth’s algorithm. We will use the 

following problem as our example: 

Calculate 5 x -3 using four bit numbers and Booth's algorithm. Show all steps neatly in a 

table. 

First, convert both numbers to binary. 

5 = 0101 

-3 = 1101 

We see that if we add 0 to the right of both binary conversions, there are four 0 to 1 or 1 to 0 

switches in 0101, and only three switches in 1101. Since three is the smaller of the two, we use 

1101 as our x value and use 0101 as out y value. The next step is to find the two's compliment of 

our y value so that we can do subtraction of y from x. We do this by keeping all 0's up until, and 

including, the first 1 the same. We then flip all the remaining bits. So two's compliment of 0101 

becomes 1011. 

The next step is to set two registers, which we name u and v, to be zero. These are going to be the 

registers where we store our product throughout the working of the problem. We then place these 

registers into a table along with two additional registers x and x-1. Register x is initially set to be the 

predetermined value of x, and x-1 is initially set to be zero. 

 u          v       x    x-1 

0000 0000 1101 0 

The next step is to look at the LSB of x and the number in the x-1 register. If the LSB of x is one, and 

x-1 is zero, we subtract y from u. If LSB of x is zero, and x-1 is 1, then we add y to u. If both LSB of 

x and x-1 are equal, you do nothing and skip to the shifting stage. In our case, the LSB of x is one, 

and x-1 is zero, so we subtract y from u. We then do an arithmetic right shift on u and v, and a 

circular right shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 

1011 

1011 

1101 1000 1110 1 

We then go through the process again using the same rules. This time we see that the LSB of x is 

0 and x-1 is 1. We must now add y to u. Once added, we then do an arithmetic right shift on u and 

v, with the last bit of v dropping off, and a circular right shift on x, also copying the LSB of x into x-1. 

This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 

1011 

1011  

1101 1000 1110 1 

0101 

0010 

0001 0100 0111 0 

Again, we repeat the process again. This time LSB of x is 1 and x-1 is zero. So like we did on the 

first pass, we subtract y from u. We then do an arithmetic right shift on u and v, and a circular right 

shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 

1011 

1011 

1101 1000 1110 1 

0101 

0010 

0001 0100 0111 0 

1011 

1100 

1110 0010 1011 1 

Now on the fourth and final pass, we see that the LSB of x is 1 and so is x-1. This makes it easier 

for us because now we don't have to add the numbers. We only have to do an arithmetic right shift 

on u and v, and a circular right shift on x, also copying the LSB of x into x-1. This gives the table: 

 u          v       x    x-1 

0000 0000 1101 0 

1011 

1011 

1101 1000 1110 1 

0101 

0010 

0001 0100 0111 0 

1011 

1100 

1110 0010 1011 1 

1111 0001 1101 1 

And we are finished. The result is u followed by v, and we get 11110001. Now to easily check our 

calculations, we take the original question, 5 x -3. This becomes -15. -15 is the two's compliment of 

15. 15 in eight bit binary is 00001111. Taking the two's compliment by the method previously 

described, we get the result 11110001, which is exactly the same as our Booths algorithm answer.