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)

Wrench

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.

Knowling

please see the update. I still don't get the result . What is wrong ? – Wrench

@grassPro: Now your S is wrong: you inverted the bits, but forgot to add 1. :-) – Knowling

yes i made a mistake.After correcting it and computing P+A in the 4th step there is a carry generated in the MSB of P+A . If i omit it i get the correct answer. But why do we have to omit it. Like in the 4th step : P+A = 110110001 + 010100000 = 1 001010001 , see the carry generated (1) in the MSB . If i omit it i will get the right answer in the next step where i have to omit the LSB of the number. – Wrench

@grassPro: Re: "why do we have to omit it": Well, because that's what the algorithm says to do. (The Wikipedia article that you linked to says to "Ignore any overflow.") If you want a deeper reason, remember that 1011 means the same as ...11111011, not ...00001011. So if you performed sign extension, this carried 1 would actually continue to carry leftward indefinitely, changing all the 1s to 0s along the way. – Knowling

@ ruakh I am getting a wrong result when i multiply 11*13 using booth algo. I get 0010001111 but i should get 10001111 . Two zeros in the MSB's are missing. Will it make a difference – Wrench

@grassPro: 0010001111 is correct. 10001111 would be incorrect, since in two's-complement notation that designates a negative number (-113). – Knowling

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

Reformer

Answer 3

5*4 =20

m=5,r=4,x=y=4

m=0101 , r=0100 , -m=1011 ,x=y=4

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

1.  P=0000 0100 0       //last two bits are 00 so simply shift P

    P=0000 0010 0

2.  P=0000 0010 0      //last two bits are 00 so simply shift P

    P=0000 0001 0

3.  P=0000 0001 0      //last two bits are 10 so perform  P = P+S

    P=1011 0001 0

    P=1101 1000 1     // after shifting P

4.  P=1101 1000 1     //last two bits are 01 so perform P = P+A

    P=0010 1000 1

    P=0001 0100 0       // after shifting P


5. now remove LSB 

   the product is P=00010100(20)

Add

Answer 4

I think x should be 2 instead of 3 -- since 3 is 11, only two bits long.

Echinus

Answer 5

Below, an implementation of Booth's Algorithm according to its flowchart illustrated in chapter 9 in the so called book "Computer Organization and Architecture, eighth edition - William Stallings. This program multiplies two numbers represented in 4 bits. When VERBOSE == 1, the program shows the different steps of the algorithm. PS: The program manipulates numbers as strings.

Good luck!

#include <stdio.h>
#define WORD 4
#define VERBOSE 1 //0

/*
 * CSC 2304 - Al Akhawayn University
 * Implementation of the Booth's Algorithm.
 */

void twosComplementAddition(char[], char[]);
void rightShift(char[], char);
void addition(char[], char[]);

char* twosComplementMultiplication(char M[], char Q[]) {
    char C;
    char *A = (char*) malloc(sizeof(char)*(2 * WORD + 1));
    char processedQ[WORD+ 1];
    char Q0, Q_1 = '0';
    int i, j;
    strcpy(A, "0000");
    if (VERBOSE) {
        printf("\n  A   |   Q   |   M   |");
        printf("\n  %s  |   %s  |   %s  |   Initial", A, Q, M);
        printf("\n-------------------------------------------------------------");
    }
    for (i = 0, j = 1; i < WORD; i++, j++) {
        Q0 = Q[WORD - 1];
        if (VERBOSE) {
            printf("\n  %s  |   %s  |   %s  |   Cycle %d", A, Q, M, j);
        }
        if (Q0 == '0' && Q_1 == '1') {
            addition(A, M);
            if (VERBOSE) {
                printf("\n  %s  |   %s  |   %s  |   Addition", A, Q, M);
            }
        } else {
            if (Q0 == '1' && Q_1 == '0') {
                twosComplementAddition(A, M);
                if (VERBOSE) {
                    printf("\n  %s  |   %s  |   %s  |   Two's Complement", A, Q, M);
                }
            }
        }
        Q_1 = Q[WORD - 1];
        rightShift(Q, A[WORD - 1]);
        rightShift(A, A[0]);
        if (VERBOSE) {
            printf("\n  %s  |   %s  |   %s  |   Right Shift", A, Q, M);
            getch();
        }
        printf("\n-------------------------------------------------------------");
    }
    strcat(A, Q);
    return A;
}
void rightShift(char reg[], char bit) {
    int i;
    for (i = WORD - 1; i > 0; i--) {
        reg[i] = reg[i - 1];
    }
    reg[0] = bit;
}

void addition(char A[], char M[]) {
    int i;
    char c = '0';
    for (i = WORD - 1; i >= 0; i--) {
        if (A[i] == '0' && M[i] == '0') {
            A[i] = c;
            c = '0';
        } else {
            if ((A[i] == '1' && M[i] == '0') || (A[i] == '0' && M[i] == '1')) {
                if (c == '0') {
                    A[i] = '1';
                } else {
                    A[i] = '0';
                }
            } else {
                if (A[i] == '1' && M[i] == '1') {
                    A[i] = c;
                    c = '1';
                }
            }
        }
    }
}
void twosComplementAddition(char A[], char M[]) {
    int i;
    char temp[WORD + 1];
    for (i = 0; i < WORD; i++) {
        if (M[i] == '0') {
            temp[i] = '1';
        } else {
            temp[i] = '0';
        }
    }
    temp[WORD] = '\0';
    addition(temp, "0001");
    addition(A, temp);
}

int main() {
    char QQ[WORD + 1];
    char M[WORD + 1];
    char Q[WORD + 1];
    char *result;

    printf("\nBooth's Algorithm");
    printf("\n*****************");
    printf("\nEnter M: ");
    scanf("%s", M);
    printf("\nEnter Q: ");
    scanf("%s", Q);
    strcpy(QQ, Q);
    result = twosComplementMultiplication(M, Q);
    printf("\n%s * %s = %s", M, QQ, result);

    printf("\n");
    return 0;

}

Dystopia

Answer 6

It is always advised to use X+1 bits for an X-bit number multiplication using Booth's algorithm. The extra one bit is used to handle the sign values. That is one problem with your approach. Without that a number like 101 (decimal:5) acts as negative 1.

Weaken

Answer 7

The Booth's Algorithm is used for the multiplication of signed numbers either one of them should be signed or both of them signed. we can't apply the Booth's Algorithm for two unsigned numbers.

Prat

Answer 8

The Booth's Algorithm is used for the multiplication of signed numbers either one of them should be signed or both of them signed. we can also apply the Booth's Algorithm for two unsigned numbers but we have to check whether the numbers are in a given range. For example if we take 4 bit numbers like 2*3 is possible .If we do 9*4 or 9*-4 or -9*-4 is not possible because 9 or -9 is not in the range of 4 bit numbers, so booth algorithm multiplication is not possible.

Tilney