Является ли алгоритм умножения стенда для умножения 2 положительных чисел?

Question

Является ли алгоритм стенда для умножения только для умножения 2 отрицательных чисел (-3 * -4) или одного положительного и одного отрицательного числа (-3 * 4)?Всякий раз, когда я умножаю 2 положительных числа, используя алгоритм стенда, я получаю неверный результат.

пример: 5 * 4

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

S = 011 0000 // 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 дополнения m

r = 4

1. После сдвига вправо P на 1 бит 0 000 100

2. После сдвига вправо P на 1 бит 0 000 010

3. P + S = 011 001 0

   После сдвига вправо на 1 бит0 011 001

4. Отказ от LSB 001100

   Но получается двоичный код из 12.Это должно было быть 20 (010100)

ОБНОВЛЕНИЕ после @ ruakh ответа

5 * 4 = 20

m = 0101 is 5

r = 0100 is 4

A = 0101 0000 0

S = 1010 0000 0

P = 0000 0100 0

1. сдвиг P вправо на 1 бит: 0 0000 0100

2. сдвиг P вправо на 1 бит: 0 0000 0010

3. P + S = 10100010 Сдвиг вправо на 1 бит: 1101 0001

4. P + A = 1 0010 0001 here 1 is the carry generated смещение вправо на 1 бит: 110010000

Оставьте LSB: 11001000 (не равно 20)

Answer 1

У вас недостаточно места для обработки вывесок. 5 - это не 101, а 0101: оно должно начинаться с 0, поскольку значения, начинающиеся с 1, являются отрицательными. 101 на самом деле -3: это дополнение к 100 *, равное 3. Аналогично, 4 - это не 100, а 0100; 100 - это -4. Поэтому, когда вы умножаете 101 на 100, вы фактически умножаете -3 на -4; вот почему вы получаете 12.

Answer 2

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)

Answer 3

Алгоритм Бута предназначен для целых чисел со знаком, то есть каждое из них может быть либо положительным, либо отрицательным, либо нулевым.

Вот пример программы на C, которая иллюстрирует как реализацию, так и промежуточные результаты умножения двух 8-битных целых чисел со знаком (2-х дополнений) и получения 16-битного продукта со знаком:

#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;
}

Выход:

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

Answer 4

Алгоритм Бута используется для умножения чисел со знаком, либо один из них должен быть подписан, либо оба подписаны. мы также можем применить алгоритм Бута для двух чисел без знака, но мы должны проверить, находятся ли числа в заданном диапазоне. Например, если мы берем 4-битные числа, такие как 2 * 3 возможны. Если мы делаем 9 * 4 или 9 * -4 или -9 * -4, это невозможно, потому что 9 или -9 не находятся в диапазоне 4-битных чисел, поэтому умножение алгоритма на стенде невозможно.

Answer 5

Алгоритм Бута используется для умножения чисел со знаком, либо один из них должен быть подписан, либо оба подписаны. мы не можем применить алгоритм Бута для двух чисел без знака.

Answer 6

Всегда рекомендуется использовать X + 1 бит для умножения чисел X-бит с использованием алгоритма Бута. Дополнительный бит используется для обработки значений знака. Это одна проблема с вашим подходом. Без этого число типа 101 (десятичное: 5) действует как отрицательное 1.

Answer 7

Ниже приведена реализация алгоритма Бута в соответствии с его блок-схемой, показанной в главе 9 в так называемой книге «Организация и архитектура компьютеров, восьмое издание - Уильям Сталлингс». Эта программа умножает два числа, представленные в 4 битах. Когда VERBOSE == 1, программа показывает различные шаги алгоритма. PS: программа манипулирует числами как строками.

Удачи!

#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;

}

Answer 8

Я думаю, x должно быть 2 вместо 3 - поскольку 3 равно 11, только два бита.