Menu
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
After right shift of P by 1 bit 0 000 100
After right shift of P by 1 bit 0 000 010
P+S = 011 001 0
After right shift by 1 bit 0 011 001
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
shift P right by 1 bit : 0 0000 0100
shift P right by 1 bit : 0 0000 0010
P+S = 10100010 Shifting rightby 1 bit : 1101 0001
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)
879
Booth's algorithm is a multiplication algorithm that multiplies two signed binary numbers in 2's complement notation. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are used. Efficient multiplication algorithms have existed since the advent of the decimal system.
Booth algorithm gives a procedure for multiplying binary integers in signed 2's complement representation in efficient way, i.e., less number of additions/subtractions required.
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.
159
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
