In this guide, we will explore Booth's algorithm and demonstrate how to implement it using the C programming language.
Booth's Algorithm
These observations form the basis of Booth's algorithm:
- It is possible to use left shift operations to multiply by two.
- Right-shift operations like division by two are possible.
- If a binary number consists of a string of consecutive 1s and then 0s , we can replace this string with a single 1 and then the same amount of 0s , and the resulting number will be equal to the original number.
These findings enable the following steps to be used to define Booth's algorithm:
- Set the item's initial value to 0 .
- Consider expressing the two binary numbers that will be multiplied as two's complements.
- To make the multiplier's length equal to the multiplicand's length, add a zero bit to the right of the multiplier.
- Examine two bits at a time, beginning with the multiplier's rightmost bit.
- Subtract the multiplicand from the product if the first two bits are 0 and 1s .
- If both bits are 1 and 0 , double the product by the multiplicand.
- Right-shift the multiplier by one bit.
- Up until all multiplier bits have been checked, repeat steps 4-7 .
Application in C
Let's now implement Booth's algorithm in the C programming language following the demonstration we just observed. We will define a function that takes two signed binary numbers as parameters and returns their sum.
The function is designed to take in two parameters: a reference to a list representing the multiplicand and the multiplier. Both lists will have a length of n bits, representing each number. It is assumed that the lists are already in two's complement format.
Let's examine the implementation of the function to gain a better understanding:
#include <stdio.h>
#include <stdlib.h>
int* booth_multiplication(int* m, int* q, int n) {
int* product = (int*) malloc(2 * n * sizeof(int));
for (int i = 0; i < 2 * n; i++) {
product[i] = 0;
}
int* a = (int*) malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
a[i] = 0;
}
int q0 = 0;
for (int i = 0; i < n; i++) {
if (q0 == 0 && q[n-1] == 1) {
for (int j = 0; j < n; j++) {
if (a[j] == 0) {
a[j] = m[j];
}
else {
a[j] = ~m[j] + 1;
}
}
}
else if (q0 == 1 && q[n-1] == 0) { // Case 2: q0 = 1, q[n-1] = 0
for (int j = 0; j < n; j++) {
if (a[j] == 0) {
a[j] = ~m[j] + 1;
}
else {
a[j] = m[j];
}
}
}
q0 = q[n-1];
for (int j = n-1; j > 0; j--) {
q[j] = q[j-1];
a[j] = a[j-1];
}
q[0] = a[0];
}
for (int i = 0; i < n; i++) {
product[i] = a[i];
}
free(a);
return product;
}
To grasp its functionality, we will now proceed with a detailed walkthrough of this particular implementation, breaking it down into individual steps.
Our initial action involves assigning memory to the product and arrays. Unlike a regular array that holds the register value used in the process, the product array will store the final result of the multiplication. The initialization value for both arrays is set to 0.
int* product = (int*) malloc(2 * n * sizeof(int));
for (int i = 0; i < 2 * n; i++) {
product[i] = 0;
}
int* a = (int*) malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
a[i] = 0;
}
Next, we execute Booth's algorithm by cycling through each individual bit of the multiplier. We make use of two variables, q0 and q[n-1], to keep a record of the latest and previous bits of the multiplier.
int q0 = 0;
for (int i = 0; i < n; i++) {
if (q0 == 0 && q[n-1] == 1) {
// Case 1: q0 = 0, q[n-1] = 1
// Add multiplicand to a if a[j] = 0
// Subtract multiplicand from a if a[j] = 1
}
else if (q0 == 1 && q[n-1] == 0) {
// Case 2: q0 = 1, q[n-1] = 0
// Subtract multiplicand from a if a[j] = 0
// Add multiplicand to a if a[j] = 1
}
// Shift a and q to the right
q0 = q[n-1];
for (int j = n-1; j > 0; j--) {
q[j] = q[j-1];
a[j] = a[j-1];
}
q[0] = a[0];
}
In every iteration, we compare the present and previous sections of the multiplier with one of two scenarios: when q0 = 0 and q[n-1] = 1, or when q0 = 1 and q[n-1] = 0. Following this comparison, based on the current bit of a, we perform the required action on the a register by either adding or subtracting the multiplicand.
The present value in the a register is transferred to the least significant position of q following a right shift of both a and q by one bit. This process is repeated for each bit of the multiplier.
After releasing the memory used by the a register and transferring its data to the product array, we then proceed to deliver the product array.
for (int i= 0; i < n; i++) {
product[i] = a[i];
}
free(a);
return product;
Example:
Here is the code for the C program that implements Booth's algorithm to perform multiplication on two signed values. The program has been compiled and run successfully. Additionally, the program output is provided below.
#include <stdio.h>
#include <math.h>
int a = 0,b = 0, c = 0, a1 = 0, b1 = 0, com[5] = { 1, 0, 0, 0, 0};
int anum[5] = {0}, anumcp[5] = {0}, bnum[5] = {0};
int acomp[5] = {0}, bcomp[5] = {0}, pro[5] = {0}, res[5] = {0};
void binary(){
a1 = fabs(a);
b1 = fabs(b);
int r, r2, i, temp;
for (i = 0; i < 5; i++){
r = a1 % 2;
a1 = a1 / 2;
r2 = b1 % 2;
b1 = b1 / 2;
anum[i] = r;
anumcp[i] = r;
bnum[i] = r2;
if(r2 == 0){
bcomp[i] = 1;
}
if(r == 0){
acomp[i] =1;
}
}
c = 0;
for ( i = 0; i < 5; i++){
res[i] = com[i]+ bcomp[i] + c;
if(res[i] >= 2){
c = 1;
}
else
c = 0;
res[i] = res[i] % 2;
}
for (i = 4; i >= 0; i--){
bcomp[i] = res[i];
}
if (a < 0){
c = 0;
for (i = 4; i >= 0; i--){
res[i] = 0;
}
for ( i = 0; i < 5; i++){
res[i] = com[i] + acomp[i] + c;
if (res[i] >= 2){
c = 1;
}
else
c = 0;
res[i] = res[i]%2;
}
for (i = 4; i >= 0; i--){
anum[i] = res[i];
anumcp[i] = res[i];
}
}
if(b < 0){
for (i = 0; i < 5; i++){
temp = bnum[i];
bnum[i] = bcomp[i];
bcomp[i] = temp;
}
}
}
void add(int num[]){
int i;
c = 0;
for ( i = 0; i < 5; i++){
res[i] = pro[i] + num[i] + c;
if (res[i] >= 2){
c = 1;
}
else{
c = 0;
}
res[i] = res[i]%2;
}
for (i = 4; i >= 0; i--){
pro[i] = res[i];
printf("%d",pro[i]);
}
printf(":");
for (i = 4; i >= 0; i--){
printf("%d", anumcp[i]);
}
}
void arshift(){
int temp = pro[4], temp2 = pro[0], i;
for (i = 1; i < 5 ; i++){
pro[i-1] = pro[i];
}
pro[4] = temp;
for (i = 1; i < 5 ; i++){
anumcp[i-1] = anumcp[i];
}
anumcp[4] = temp2;
printf("\nAR-SHIFT: ");
for (i = 4; i >= 0; i--){
printf("%d",pro[i]);
}
printf(":");
for(i = 4; i >= 0; i--){
printf("%d", anumcp[i]);
}
}
void main(){
int i, q = 0;
printf("\t\tBOOTH'S MULTIPLICATION ALGORITHM");
printf("\nEnter two numbers to multiply: ");
printf("\nBoth must be less than 16");
//simulating for two numbers each below 16
do{
printf("\nEnter A: ");
scanf("%d",&a);
printf("Enter B: ");
scanf("%d", &b);
}while(a >=16 || b >=16);
printf("\nExpected product = %d", a * b);
binary();
printf("\n\nBinary Equivalents are: ");
printf("\nA = ");
for (i = 4; i >= 0; i--){
printf("%d", anum[i]);
}
printf("\nB = ");
for (i = 4; i >= 0; i--){
printf("%d", bnum[i]);
}
printf("\nB'+ 1 = ");
for (i = 4; i >= 0; i--){
printf("%d", bcomp[i]);
}
printf("\n\n");
for (i = 0;i < 5; i++){
if (anum[i] == q){
printf("\n-->");
arshift();
q = anum[i];
}
else if(anum[i] == 1 && q == 0){
printf("\n-->");
printf("\nSUB B: ");
add(bcomp);
arshift();
q = anum[i];
}
else{
printf("\n-->");
printf("\nADD B: ");
add(bnum);
arshift();
q = anum[i];
}
}
printf("\nProduct is = ");
for (i = 4; i >= 0; i--){
printf("%d", pro[i]);
}
for (i = 4; i >= 0; i--){
printf("%d", anumcp[i]);
}
}
Output:
BOOTH'S MULTIPLICATION ALGORITHM
Enter two numbers to multiply:
Both must be less than 16
Enter A: 1
Enter B: 11
Expected product = 11
Binary Equivalents are:
A = 00001
B = 01011
B'+ 1 = 10101
-->
SUB B: 10101:00001
AR-SHIFT: 11010:10000
-->
ADD B: 00101:10000
AR-SHIFT: 00010:11000
-->
AR-SHIFT: 00001:01100
-->
AR-SHIFT: 00000:10110
-->
AR-SHIFT: 00000:01011
Product is = 0000001011
Conclusion:
In summary, the Booth algorithm proves to be a valuable method for performing binary multiplication on signed integers represented in 2's complement. In contrast to traditional multiplication methods, this approach simplifies the process by involving shifts and selectively adding or subtracting the multiplicand depending on the multiplier bit. Our provided C implementation of Booth's algorithm relies on bitwise operations and includes a real-world scenario for demonstration.