C Program To Implement Booth’s Algorithm
Learn how to implement Booth’s Algorithm in C Programming Language. This algorithm is also famously known as Booth’s Multiplication Algorithm named after Andrew Donald Booth. The below given code makes use of arrays and binary and decimal conversions.
What is Booth’s Algorithm?
Booth’s Algorithm is a multiplication algorithm for multiplying two signed binary numbers in two’s complement notation. The booth’s multiplication algorithm is primarily used in computer architectures. Shifting bits is comparatively faster than adding digits and, therefore, this algorithm has a faster speed of calculation.
Booth’s Algorithm can be done using different methods such as Right-Shift Arithmetic and Right-Shift Circulant. The booth’s multiplication algorithm helps in fast multiplication and signed multiplication.
The right shift arithmetic method involves addition of two binary numbers and shift the resultant sum to 1 bit right position. This C Program Implementation of Booth’s Algorithm uses Right Shift Arithmetic method. The right shift circulant method involves shifting the bits to the right 1 bit position and take the last bit in the binary string and append it to the start of the same binary string.
Must Read: C Program For Queens Algorithm Problem
This algorithm can be implemented adding one of the two predetermined x and y to get a product. This addition will be unsigned binary addition. After this, a rightward arithmetic shift on the final product is to be done. After getting the final result, convert the two’s complement of the product of decimal number.
Must Read: C Program To Implement Dijkstra’s Algorithm using Adjacency Matrix
C Program For Booth’s Algorithm For Signed Multiplication
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 | #include<stdio.h> #include<math.h> void binary(); void sum(int num[]); void arithmetic_shift(); int comparison[5] = {1, 0, 0, 0, 0}; int first_number[5] = {0}, second_number[5] = {0}, anumcp[5] = {0}; int compare_num1[5] = {0}, compare_num2[5] = {0}, product[5] = {0}, result[5] = {0}; int num1 = 0, num2 = 0, num3 = 0; int m = 0, n = 0; int main() { int count, x = 0; printf("Enter Two Numbers to Multiply (Less Than 16)\n"); do { printf("Enter A:\t"); scanf("%d", &num1); printf("Enter B:\t"); scanf("%d", &num2); }while(num1 >=16 || num2 >=16); printf("\nExpected Product of %d * %d = %d", num1, num2, num1 * num2); binary(); printf("\n\nBinary Equivalents\n"); printf("\nA:\t"); for(count = 4; count >= 0; count--) { printf("%d", first_number[count]); } printf("\nB:\t"); for(count = 4; count >= 0; count--) { printf("%d", second_number[count]); } printf("\nB'+ 1 = "); for(count = 4; count >= 0; count--) { printf("%d", compare_num2[count]); } printf("\n"); for(count = 0; count < 5; count++) { if(first_number[count] == x) { printf("\n-->"); arithmetic_shift(); x = first_number[count]; } else if(first_number[count] == 1 && x == 0) { printf("\n-->"); printf("\nSUB B: "); sum(compare_num2); arithmetic_shift(); x = first_number[count]; } else { printf("\n-->"); printf("\nADD B: "); sum(second_number); arithmetic_shift(); x = first_number[count]; } } printf("\nProduct:\t"); for(count = 4; count >= 0; count--) { printf("%d", product[count]); } for(count = 4; count >= 0; count--) { printf("%d", anumcp[count]); } printf("\n"); return 0; } void binary() { m = fabs(num1); n = fabs(num2); int r2, remainder, count, temp; for(count = 0; count < 5; count++) { remainder = m % 2; m = m / 2; r2 = n % 2; n = n / 2; first_number[count] = remainder; anumcp[count] = remainder; second_number[count] = r2; if(r2 == 0) { compare_num2[count] = 1; } if(remainder == 0) { compare_num1[count] =1; } } num3 = 0; for(count = 0; count < 5; count++) { result[count] = comparison[count]+ compare_num2[count] + num3; if(result[count] >= 2) { num3 = 1; } else { num3 = 0; } result[count] = result[count] % 2; } for(count = 4; count >= 0; count--) { compare_num2[count] = result[count]; } if(num1 < 0) { num3 = 0; for(count = 4; count >= 0; count--) { result[count] = 0; } for(count = 0; count < 5; count++) { result[count] = comparison[count] + compare_num1[count] + num3; if(result[count] >= 2) { num3 = 1; } else { num3 = 0; } result[count] = result[count] % 2; } for(count = 4; count >= 0; count--) { first_number[count] = result[count]; anumcp[count] = result[count]; } } if(num2 < 0) { for(count = 0; count < 5; count++) { temp = second_number[count]; second_number[count] = compare_num2[count]; compare_num2[count] = temp; } } } void sum(int num[]) { int count; num3 = 0; for(count = 0; count < 5; count++) { result[count] = product[count] + num[count] + num3; if(result[count] >= 2) { num3 = 1; } else { num3 = 0; } result[count] = result[count] % 2; } for(count = 4; count >= 0; count--) { product[count] = result[count]; printf("%d", product[count]); } printf(":"); for(count = 4; count >= 0; count--) { printf("%d", anumcp[count]); } } void arithmetic_shift() { int x = product[4], y = product[0], count; for(count = 1; count < 5 ; count++) { product[count - 1] = product[count]; } product[4] = x; for(count = 1; count < 5; count++) { anumcp[count - 1] = anumcp[count]; } anumcp[4] = y; printf("\nArithmetic Shift"); for(count = 4; count >= 0; count--) { printf("%d", product[count]); } printf(":"); for(count = 4; count >= 0; count--) { printf("%d", anumcp[count]); } } |
Must Read: C Program For Kruskal’s Algorithm For Minimum Spanning Tree
Output
If you have any compilation errors or doubts in this C Program for Booth’s Multiplication Algorithm Implementation, let us know about it in the comment section below.
The Booth’s algorithm is really difficult to understand. Normal additiin is good. 😛
I had not heard of Booth’ algorithm before. This is something new for me.
Shifting of bits or bit manipulation is faster than actual addition of integers. Therefore, this algorithm works so fast.