Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is booth algorithm for multiplication only for multiplying 2 negative numbers (-3 * -4) or one positive and one negative number (-3 * 4) ? Whenever i multiply 2 positive numbers using booth algorithm i get a wrong result.

example : 5 * 4

A = 101 000 0 // binary of 5 is 101

S = 011 000 0 // 2's complement of 5 is 011

P = 000 100 0 // binary of 4 is 100

x = 3

y = 3

m = 5

-m = 2's complement of m

r = 4

  1. After right shift of P by 1 bit 0 000 100

  2. After right shift of P by 1 bit 0 000 010

  3. P+S = 011 001 0

    After right shift by 1 bit 0 011 001

  4. Discarding the LSB 001100

    But that comes out to be the binary of 12 . It should have been 20(010100)

share|improve this question
add comment

1 Answer

The problem is you are using 3 bits for m and r, and they must be represented using 4 bits to get unsigned values. (Using just 3 bits, 101 = -3 and 100 = -4, and the result does = 12).

So redoing this with 4 bits, one gets:

example : 5 * 4

A = 0101 0000 0 // binary of 5 is 0101

S = 1011 0000 0 // 2's complement of 5 is 1011

P = 0000 0100 0 // binary of 4 is 0100

x = 4

y = 4

m = 5

-m = 2's complement of m

r = 4

1.    After right shift of P by 1 bit 0000 0010 0

2.    After right shift of P by 1 bit 0000 0001 0

3.    P+S = 1011 0001 0

      After right shift by 1 bit 0101 1000 1

4.    P+A = 0010 1001 0     (not 1010 1001 0, since overflow in MSB is ignored)

      After right shift by 1 bit 0001 0100 1

Discarding the LSB gives 00010100   which is 20

which gives the correct answer.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.