2
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ no doubt brain fade on my part (VERY long day) BUT why is 5 shown as $50 throughout and 4 shown as $04 and nobody seems to mind.|$50 x $04 will not give you $20. (It probably gives $40 with carry. Has my brain melted (happens occasionally) or has the emperor got no clothes on? \$\endgroup\$
    – Russell McMahon
    Nov 19 '11 at 9:53
  • \$\begingroup\$ @Russell - I think the emperor is in possession of his habiliments :-) Have a look at the Wiki page linked to in the question (see "A typical implementation", number 1) It gives the details of how to set up A, S and P. \$\endgroup\$
    – Oli Glaser
    Nov 19 '11 at 12:09
0
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ The simplest way to explain why multiplying two signed numbers gives a shorter number is to consider the signed numbers as (a-k) and (b-k) (for 16-bit numbers, k=32768). Note that the inversion of the top bit doesn't affect anything. The value of (a-k)*(b-k) is ab+kk-(a+b)*k. Since a and b are positive numbers in the range 0..k-1, this formula generates a range which folds back on itself. \$\endgroup\$
    – supercat
    Nov 19 '11 at 18:48
  • \$\begingroup\$ I think that it's even simpler if you consider that 8 bit signed variables are 1+7 bits; multiplying 2 of them, you obtain a 1+7+7=15 variable, as the signs multiply to get the sign of the result. \$\endgroup\$
    – clabacchio
    Feb 17 '12 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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