Booth vs Add&SHIFT Calculation?

Question

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.

Answer 1

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

Comments

Very well Explained thanks bruh.

---

I didnt expected this mistake from you sorry.

---

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.

Answer 2

http://profile.iiita.ac.in/bibhas.ghoshal/lecture_slides_coa/computer_arithmetic.pdf

Comments

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.