Is booth multiplication algorithm for multiplying 2 positive numbers?

Question

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 number of bits in m

y = 3 number of bits in r

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)

UPDATE after @ ruakh answer

5 * 4 = 20

m = 0101 is 5

r = 0100 is 4

A = 0101 0000 0

S = 1010 0000 0

P = 0000 0100 0

1. shift P right by 1 bit : 0 0000 0100

2. shift P right by 1 bit : 0 0000 0010

3. P+S = 10100010 Shifting rightby 1 bit : 1101 0001

4. P+A = 1 0010 0001 here 1 is the carry generated shifting right by 1 bit : 110010000

Leave the LSB : 11001000 (not equal to 20)

Answer 1

You're not giving enough room for your sign handling. 5 is not 101, but 0101: it has to start with a 0, because values starting with 1 are negative. 101 is actually -3: it's the two's complement of 011, which is 3. Similarly, 4 is not 100, but 0100; 100 is -4. So when you multiply 101 by 100, you're actually multiplying -3 by -4; that's why you get 12.

Answer 2

Booth's algorithm is for signed integers, that is, each can be either positive or negative or zero.

Here's a sample C program that illustrates both an implementation and intermediate results of multiplying two 8-bit signed (2's complement) integers and getting a 16-bit signed product:

#include <stdio.h>
#include <limits.h>
#include <string.h>

typedef signed char int8;
typedef short int16;

char* Num2BaseStr(unsigned long long num, unsigned base, int maxDigits)
{
  static char s[sizeof(num) * CHAR_BIT + 1];
  char* p = &s[sizeof(s) - 1];

  memset(s, 0, sizeof(s));

  do
  {
    *--p = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[num % base];
    num /= base;
  } while ((num != 0) || (p > s));

  // Keep at most maxDigits digits if requested
  if ((maxDigits >= 0) && (&s[sizeof(s) - 1] - p > maxDigits))
  {
    p = &s[sizeof(s) - 1] - maxDigits;
  }
  // Skip leading zeroes otherwise
  else
  {
    while (*p == '0') p++;
  }

  return p;
}

int16 BoothMul(int8 a, int8 b)
{
  int16 result = 0;
  int16 bb = b;
  int f0 = 0, f1;
  int i = 8;

  printf("a = %sb (%d)\n", Num2BaseStr(a, 2, 8), a);
  printf("b = %sb (%d)\n", Num2BaseStr(b, 2, 8), b);
  printf("\n");

  while (i--)
  {
    f1 = a & 1;
    a >>= 1;

    printf("        %sb\n", Num2BaseStr(result, 2, 16));
    printf("(%d%d)  ", f1, f0);
    if (!f1 && f0)
    {
      printf("+ %sb\n", Num2BaseStr(bb, 2, 16));
      result += bb;
    }
    else if (f1 && !f0)
    {
      printf("- %sb\n", Num2BaseStr(bb, 2, 16));
      result -= bb;
    }
    else
    {
      printf("no +/-\n");
    }
    printf("\n");

    bb <<= 1;

    f0 = f1;
  }

  printf("a * b = %sb (%d)\n", Num2BaseStr(result, 2, 16), result);

  return result;
}

int main(void)
{
  const int8 testData[][2] =
  {
    {  4,  5 },
    {  4, -5 },
    { -4,  5 },
    { -4, -5 },
    {  5,  4 },
    {  5, -4 },
    { -5,  4 },
    { -5, -4 },
  };
  int i;

  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
    printf("%d * %d = %d\n\n",
           testData[i][0],
           testData[i][1],
           BoothMul(testData[i][0], testData[i][1]));

  return 0;
}

Output:

a = 00000100b (4)
b = 00000101b (5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 0000000000010100b

        1111111111101100b
(01)  + 0000000000101000b

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

a * b = 0000000000010100b (20)
4 * 5 = 20

a = 00000100b (4)
b = 11111011b (-5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 1111111111101100b

        0000000000010100b
(01)  + 1111111111011000b

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

a * b = 1111111111101100b (-20)
4 * -5 = -20

a = 11111100b (-4)
b = 00000101b (5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 0000000000010100b

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

a * b = 1111111111101100b (-20)
-4 * 5 = -20

a = 11111100b (-4)
b = 11111011b (-5)

        0000000000000000b
(00)  no +/-

        0000000000000000b
(00)  no +/-

        0000000000000000b
(10)  - 1111111111101100b

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

a * b = 0000000000010100b (20)
-4 * -5 = 20

a = 00000101b (5)
b = 00000100b (4)

        0000000000000000b
(10)  - 0000000000000100b

        1111111111111100b
(01)  + 0000000000001000b

        0000000000000100b
(10)  - 0000000000010000b

        1111111111110100b
(01)  + 0000000000100000b

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

        0000000000010100b
(00)  no +/-

a * b = 0000000000010100b (20)
5 * 4 = 20

a = 00000101b (5)
b = 11111100b (-4)

        0000000000000000b
(10)  - 1111111111111100b

        0000000000000100b
(01)  + 1111111111111000b

        1111111111111100b
(10)  - 1111111111110000b

        0000000000001100b
(01)  + 1111111111100000b

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

        1111111111101100b
(00)  no +/-

a * b = 1111111111101100b (-20)
5 * -4 = -20

a = 11111011b (-5)
b = 00000100b (4)

        0000000000000000b
(10)  - 0000000000000100b

        1111111111111100b
(11)  no +/-

        1111111111111100b
(01)  + 0000000000010000b

        0000000000001100b
(10)  - 0000000000100000b

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

        1111111111101100b
(11)  no +/-

a * b = 1111111111101100b (-20)
-5 * 4 = -20

a = 11111011b (-5)
b = 11111100b (-4)

        0000000000000000b
(10)  - 1111111111111100b

        0000000000000100b
(11)  no +/-

        0000000000000100b
(01)  + 1111111111110000b

        1111111111110100b
(10)  - 1111111111100000b

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

        0000000000010100b
(11)  no +/-

a * b = 0000000000010100b (20)
-5 * -4 = 20