¿El algoritmo de multiplicación de casetas para multiplicar 2 números positivos?

2

Es el Algoritmo Booth para la multiplicación solo para multiplicar dos números negativos como \ $ - 3 * -4 \ $ o también puede multiplicar un número positivo y otro negativo, como \ $ - 3 * 4 \ $? Creo que no es para multiplicar dos números positivos, cuando multiplico 2 números positivos utilizando el algoritmo de cabina, obtengo un resultado incorrecto.

Por ejemplo: \ $ 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. Después del desplazamiento a la derecha de P por 1 bit 0 000 100

  2. Después del desplazamiento a la derecha de P por 1 bit 0 000 010

  3. P + S = 011 001 0

    Después del desplazamiento a la derecha por 1 bit 0 011 001

  4. Descartando el LSB 001100

    Pero eso resulta ser el binario de 12. Debería haber sido 20 (010100)

pregunta grassPro

2 respuestas

1

Creo que es porque estás usando 3 bits, y para 3 bits no hay complemento de 5.
Pruébalo con 4 bits. Acabo de probarlo y parece funcionar para mí.

Aquí hay un ejemplo:

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

1er paso

Los últimos 2 dígitos de P son 00, por lo que arithmetic a la derecha desplazamos dando:

P = 0000 0010 0

Segundo paso

Los últimos 2 dígitos de P son 00, así que cambiamos a la derecha dando:

P = 0000 0001 0

3er paso

Los últimos 2 dígitos de P son 10, por lo que agregamos P a S para dar:

P = 1011 0000 1

Luego, a la derecha, da:
P = 1101 1000 1 (note la replicación de MSB, por lo que 1 se desplaza)

Cuarto paso

Los últimos 2 dígitos de P son 01, por lo que agregamos P a A para dar:

P = 0010 1000 1

Luego da vuelta a la derecha dando:
    P = 0001 0100 0

Luego, finalmente, elimine el LSB dando:

0001 0100 = 20
Cual es el producto de 4 * 5.

    
respondido por el Oli Glaser
0

EDIT : Me equivoqué cuando dije que Booths no hace números negativos. Debo haberlo confundido con algún otro algoritmo de multiplicación. Aun así, el resto de esta respuesta no se modificará, ya que todavía contiene información útil.

Usted respondió su propia pregunta. No, no funciona. La mayoría de los algoritmos de multiplicación no funcionan con números negativos. Algunos pueden modificarse para que funcionen, usando cuidadosamente las extensiones de signo y demás. Pero la mayoría requiere un "envoltorio" alrededor de ellos que convierta las entradas a unsigned, haga la multiplicación y luego convierta el producto a firmado según el signo de los números de entrada.

Mientras estás tratando con números firmados, hay otra cosa que debes tener en cuenta ...

Si multiplicas dos números NO FIRMADOS de 8 bits, el resultado es un número de 16 bits. ¡Pero si multiplicas dos números de 8 bits FIRMADOS, el resultado es un número de 15 bits! Normalmente, ese número de 15 bits se "ampliará" a un número de 16 bits, pero en realidad es solo de 15 bits.

Es un poco difícil de explicar qué está pasando matemáticamente. Tuve que sacar una calculadora y simplemente probar un montón de ejemplos para convencerme de esto. Ahora lo entiendo, pero no puedo explicarlo. Las páginas web que he leído sobre esto eran terribles y tampoco lo explicaban muy bien. Normalmente, esta pequeña diferencia no importa mucho, pero sí importa bastante si está multiplicando números de punto fijo (en lugar de números enteros o de punto flotante).

    
respondido por el user3624

Lea otras preguntas en las etiquetas