Is booth multiplication algorithm for multiplying 2 positive numbers?

Question

Is the Booth algorithm for multiplication only for multiplying two negative numbers such as \$-3 * -4\$ or can it also multiply one positive and one negative number such as \$-3 * 4\$? I believe that it's not for multiplying two positive numbers, whenever I multiply 2 positive numbers using booth algorithm i get a wrong result.

For 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)

Answer 1

I think it is because you are using 3 bits, and for 3 bits there is no complement of 5.
Try it with 4 bits. I just tried it and it seems to work for me.

Here's an example:

A = 0101 0000 0
S = 1011 0000 0
P = 0000 0100 0

1st step

Last 2 digits of P are 00 so we arithmetic right shift giving:

P = 0000 0010 0

2nd step

Last 2 digits of P are 00 so we right shift giving:

P = 0000 0001 0

3rd step

Last 2 digits of P are 10 so we add P to S giving:

P = 1011 0000 1

Then right shift giving:
P = 1101 1000 1 (note the MSB replication so 1 is shifted in)

4th step

Last 2 digits of P are 01 so we add P to A giving:

P = 0010 1000 1

Then right shift giving:
P = 0001 0100 0

Then finally remove the LSB giving:

0001 0100 = 20
Which is the product of 4 * 5.

Answer 2

EDIT: I was mistaken when I said that Booths doesn't do negative numbers. I must have confused it with some other multiplication algorithm. Even so, I'm leaving the remainder of this answer unchanged, since there is still some useful info in it.

You answered your own question. No, it doesn't work. Most multiplication algorithms don't work with negative numbers. Some can be modified to work, carefully using sign-extensions and such. But most require a "wrapper" around them that converts the inputs to unsigned, does the multiplication, and then converts the product to signed based on the sign of the input numbers.

While you're dealing with signed numbers, here's another thing you keep in mind...

If you multiply two 8-bit UNSIGNED numbers, the result is a 16 bit number. But if you multiply two SIGNED 8-bit numbers, the result is a 15 bit number! Normally that 15 bit number will be "extended" to a 16 bit number, but it is really only 15 bits.

It's a little hard to explain what's going on, mathematically. I had to get out a calculator and simply try a bunch of examples to convince myself of this. Now I understand it, but I can't explain it. The web pages I've read about this were terrible and didn't explain it very well either. Normally this small difference doesn't matter much, but it does matter quite a bit if you are multiplying fixed point numbers (as opposed to integer or floating point numbers).