The Gateway to Computer Science Excellence

+7 votes

70E5F867 * EFB70E1E

= 0111 0000 1110 0101 1111 1110 0110 0111

* 1110 1111 1011 0111 0000 1110 0001 1110

In normal shift addition this amounts to 20 addition as the partial product must be added corresponding to each '1' in the multiplier and we have 20 1's here.

In Booth's multiplication we do an ADD for a sequence of continuous 1's and a subtraction when the sequence ends. So, if we scan from right to left, when we encounter "10" we do a subtract and when we encounter "01" we do an ADD. But SUB is also done by adding 2's complement and this also can be counted as ADD. So, we will have 11 additions (5 + and 6 -) here which can be shown in either way as follows:

1110 1111 1011 0111 0000 1110 0001 1110 (5 ADD)

1110 1111 1011 0111 0000 1110 0001 1110 (6 SUB)

But the above works for signed numbers in 2's complement form. For unsigned numbers we have to do the same but with a '0' added to the left of multiplier thus extending its number of bits by 1. Thus we get

0 1110 1111 1011 0111 0000 1110 0001 1110 - 6 ADD

Ref: https://people.cs.pitt.edu/~jmisurda/teaching/cs447/examples/Booth%20Example.pdf

0

Isn't addition for booths algorithm is when we encounter "01" and subtraction is for "10" while scanning string from right to left. So the string for

1110 1111 1011 0111 0000 1110 0001 1110 0 (after padding with extra 0)

will be

00-1 +1 000 0 -1+10 -1 +100 -1 000 +1 00-1 0 00+1 0 00-1 0

So in total 6 subtractions and 5 additions?

0

I had given a reference for my statement. If you are contradicting please provide a valid justification/reference.

+1

Sir,

The same reference you provided

https://people.cs.pitt.edu/~jmisurda/teaching/cs447/examples/Booth%20Example.pdf

Like in example given when we see "10" we subtract and adding for "01". (marked one will be Q0 or scanned first while going from left to right.)

0

this is unsigned numbers, and in booth algorithm we must have a zero in left of the number, i.e: we have 0 1110 1111 1011 0111 0000 1110 0001 1110. just 6 add.

+1

It is a long example. So, lets do a simpler one:

$011 \times 110 (3\times -2)$. Our required answer is -6 which in 2's complement is 1010, and with 6 bits is 111010.

So, I extend the multiplier 110 as

000 110 and the extra bit to right as 0.

So, from RHS, we get '00' (considering the extra bit also), so just shift right to get

000 011 0

Now, "10", which means SUB multiplicand (to left part) and then shift. So we get

101 011 0 >>1 =

110 101 1

Now, "11". So, just shift right.

111 010 1

And we are done. (For 3 bit multiplication we have to do 3 shifts only).

So, we did just one subtraction here where out multiplier was 110 and got the correct result.

This is for signed numbers. For unsigned numbers we have to add a '0' to the left of the multiplier to begin with. So, we do $011 \times 110 (3 \times 6)$ and our expected result is $10010$.

0000 0110 0

"00", so shift right

0000 0011 0

"10", so SUB and shift

1101 0011 0 >>1 =

1110 1001 1

"11", so shift right

1111 0100 1

"01", so ADD and shift

0010 0100 1>>1=

0001 0010 0

4 shifts over and we are done. So, we did 1 SUB and 1 ADD here.

$011 \times 110 (3\times -2)$. Our required answer is -6 which in 2's complement is 1010, and with 6 bits is 111010.

So, I extend the multiplier 110 as

000 110 and the extra bit to right as 0.

So, from RHS, we get '00' (considering the extra bit also), so just shift right to get

000 011 0

Now, "10", which means SUB multiplicand (to left part) and then shift. So we get

101 011 0 >>1 =

110 101 1

Now, "11". So, just shift right.

111 010 1

And we are done. (For 3 bit multiplication we have to do 3 shifts only).

So, we did just one subtraction here where out multiplier was 110 and got the correct result.

This is for signed numbers. For unsigned numbers we have to add a '0' to the left of the multiplier to begin with. So, we do $011 \times 110 (3 \times 6)$ and our expected result is $10010$.

0000 0110 0

"00", so shift right

0000 0011 0

"10", so SUB and shift

1101 0011 0 >>1 =

1110 1001 1

"11", so shift right

1111 0100 1

"01", so ADD and shift

0010 0100 1>>1=

0001 0010 0

4 shifts over and we are done. So, we did 1 SUB and 1 ADD here.

0

hi arjun sir, does the following rule you stated always hold:

For unsigned numbers we have to add a '0' to the left of the multiplier to begin with.

I worked out your above example of $3\times 6$ with 3 bits multiplier and multiplicand (you have done this with 4 bits) and I still got same answer $18$. So I was guessing exactly when we have to add extra zero to the left of the multiplicand and multiplier. After a bit of thinking I felt that we should add extra zero only when 2's complement of either multiplicand and multiplier cannot be fitted in current number of bits. Is this correct? Please confirm since this is important as length of the operands determine how many times shifting need to be done, or better to say how many iterations need to be performed.

0 votes

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,339 answers

198,449 comments

105,205 users