¿Es el algoritmo de multiplicación de Booth para multiplicar 2 números positivos?

Question

¿Es el Algoritmo de Booth para la multiplicación sólo 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, siempre que multiplico 2 números positivos utilizando el algoritmo de booth obtengo un resultado erróneo.

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. Tras el desplazamiento a la derecha de P en 1 bit 0 000 100

2. Tras el desplazamiento a la derecha de P en 1 bit 0 000 010

3. P+S = 011 001 0

   Tras el desplazamiento a la derecha de 1 bit 0 011 001

4. Descartar el LSB 001100

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

Answer 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 que me funciona.

He aquí un ejemplo:

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

Primer paso

Los dos últimos dígitos de la P son 00, así que _aritmética_ dar el turno a la derecha:

P = 0000 0010 0

2º paso

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

P = 0000 0001 0

Tercer paso

Los últimos 2 dígitos de P son 10 por lo que sumamos P a S dando:

P = 1011 0000 1

Luego, el cambio a la derecha dando:
P = 1101 1000 1 (nótese la replicación del MSB, por lo que el 1 se desplaza hacia dentro)

4º paso

Los 2 últimos dígitos de P son 01 por lo que añadimos P a A dando:

P = 0010 1000 1

Luego, el cambio a la derecha dando:
P = 0001 0100 0

Luego, por último, eliminar el LSB dando:

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

Answer 2

EDITAR : Me equivoqué al decir que Booths no hace números negativos. Debí confundirlo con algún otro algoritmo de multiplicación. Aun así, voy a dejar el resto de la respuesta sin cambios, ya que todavía hay alguna información útil en ella.

Has respondido a tu propia pregunta. No, no funciona. La mayoría de los algoritmos de multiplicación no funcionan con números negativos. Algunos pueden ser modificados para que funcionen, utilizando cuidadosamente extensiones de signo y demás. Pero la mayoría requiere una "envoltura" alrededor de ellos que convierte las entradas a sin signo, hace la multiplicación, y luego convierte el producto a con signo basado en el signo de los números de entrada.

Mientras te ocupas de los números con signo, hay otra cosa que debes tener en cuenta...

Si se multiplican dos números de 8 bits SIN SIGNO, el resultado es un número de 16 bits. Pero si se multiplican dos números de 8 bits CON SIGNO, el resultado es un número de 15 bits. Normalmente, ese número de 15 bits se "extenderá" a un número de 16 bits, pero en realidad es sólo de 15 bits.

Es un poco difícil explicar lo que sucede, matemáticamente. He tenido que sacar una calculadora y simplemente probar un montón de ejemplos para convencerme de ello. 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ás multiplicando números de punto fijo (a diferencia de números enteros o de punto flotante).