The Gateway to Computer Science Excellence
+8 votes
1k views
We want to multiply two 32 bit unsigned numbers 70E5F867 * EFB70E1E. . how many add operation is needed in ADD-shift and Booth method? Any idea how I can solve this? the solution give a 20 and 6.
in CO and Architecture by (149 points)
retagged by | 1k views

2 Answers

+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

by Veteran (431k points)
edited by
0
very nice.... I read it more
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
Yes, you are correct- my mistake. It must be 5 ADD +6 SUB = 11.
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.
0
please read my comments.
+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.
0
what do you mean by this example?
+1
It means the answer to the question will be 6 ADD and 6 SUB due to unsigned numbers.
0
Very well Explained thanks bruh.
0
I didnt expected this mistake from you sorry.
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
by (211 points)
+2
Dear Nidhi, I read your PDF, Google it and Patterson Books, but I couldent reach to above answer. this answer should be a comment not answer, Answer means solve my problem and reach to numerical value :) thanks again, you are so nice.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,339 answers
198,449 comments
105,205 users