Turn on/off lights

Understanding Booth's Algorithm

Booth's algorithm is a non conventional approach to multiplication. Though the implementation is non challenging, I found the underlying concept a bit tricky. Here I would like to share a detailed analysis of it's working.

Multiplication is all about adding a value 'a', 'b' times. Here 'a' is called a multiplier, and 'b' is multiplicand. Example:
Let multiplicand be 3, multiplier be 15, then
3*15 = 15 + 15 + 15 = 45

Binary multiplication can be approached in a similar fashion. We can take multiplicand as a counter and can add multiplier to the accumulator, decrementing the counter at each addition. The process will stop when the counter reaches zero and the accumulator will store the result.
If you are not familiar with accumulator, think of it as a data cell initialized to 0.

Unfortunately, the above approach trades efficiency for simplicity. When we deal with low-level architecture, the no. of additions and subtractions increase the time complexity. For large numbers, the no. of additions increases drastically.
Try multiplying 253614*727128 !

To combat that, we go back to 1^st grade. The algorithm taught to us to multiply two numbers is surprisingly more efficient than the one stated above.
Let's start with an example:
Assume : multiplicand = 42, multiplier = 19

    [1]	
     4  2	
X    1  9
------------
  3  7  8
+ 4  2  
------------
  7  9  8
------------

The above example as we will observe trades inefficient additions for bitwise operations. First let us understand why this basic method works. The principle used is distributive property:
( a + b ) * ( c + d ) = a*b + a*d + b*c + b*d
( 40 + 2 ) * ( 10 + 9 ) = 40*10 + 40*9 + 2*10 + 2*9 = 798

We first divide the multiplicand and multiplier according to their place value, multiply each individual component and finally add them all. By shedding the zeros and replacing them with shift operations, we start seeing a noticeable difference in terms of no. of addition operations. Here is an excellent link to better visualize this process : [ lattice multiplication ].

By now the reader should realize that implementing this in computers will be a performance-boost as we only deal with binary digits ( 0's and 1's ). We can skip an entire row where multiplier's digit is 0. Though we would have to do more shift operations every subsequent digit, this is not a major concern as most modern processors can perform this in O(1) time. See the following SO question for more detail : [ Is bit shifting O(1) or O(n)? ]. Carry look ahead adders can be used to reduce the propagation delay in addition operations.

But can we perform better ?

How ?

A careful reader would have realized by now that this game is all about minimizing the number of addition operations. In enters the Booth's algorithm. It works on the principle that by simplifying addition operations, we can reduce the no. of 1's and in turn reduce the no. of additions. We start with accumulator initialized to 0, multiplier ( m ) with its initial value and m_-1 to 0.

With the goal of multiplying multiplier( m ) * multiplicand( n ), all we do is check m₀ and m_-1 bits at each step, where m₀ is the leftmost bit of multiplier. We then follow a simple check: ( m_-1 - m₀ ).

We can observe from the above check:

m_-1	m₀	m_-1 - m₀
1	1	0
0	0	0
1	0	1
0	1	-1

All we do now is multiply 'check' value with multiplicand and 2^a. Where 'a' is counter from 0 to no. of bits in m or n. If multiplicand and multiplier doesn't have the same number of bits, padding is required. Think of padding this way: when m : 11, n : 1010 --> m will become 0011 and no. of bits will be 4. After each step, we perform arithmetic right shift, just like we did in lattice multiplication.

Ok, so with all in place, let's try and see the final equation : ∑ ARS [ (m_k-1 - m_k) * n * 2^k ]
Where ARS is arithmetic right shift, n is multiplicand and m is the multiplier. The ARS outside square brackets indicates that arithmetic right shift has to be performed at each step.

NOTE: This equation is NOT in accordance with the mathematical convention, and I use it as a remembering technique.

You would observe that that the above equation will be equal to m*n, our result to be determined.

Helpful resources:
[1] Wikipedia
[2] https://bit.ly/2TvfUqF

Update (28/04/19): The [2] link is dead. Luckily I have a copy of the PDF file with me. If anyone is interested, I can mail it to them.

←