C++ Program to Implement Booth’s Multiplication Algorithm for Multiplication

«
»
This is a C++ Program to multiply two signed numbers using booth’s algorithm. Booth’s multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two’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.

Here is source code of the C++ Program to Implement Booth’s Multiplication Algorithm for Multiplication of 2 signed Numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<conio.h>
  3.  
  4. using namespace std;
  5.  
  6. void add(int a[], int x[], int qrn);
  7. void complement(int a[], int n)
  8. {
  9.     int i;
  10.  
  11.     int x[8] = { NULL };
  12.     x[0] = 1;
  13.     for (i = 0; i < n; i++)
  14.     {
  15.         a[i] = (a[i] + 1) % 2;
  16.     }
  17.     add(a, x, n);
  18. }
  19.  
  20. void add(int ac[], int x[], int qrn)
  21. {
  22.     int i, c = 0;
  23.     for (i = 0; i < qrn; i++)
  24.     {
  25.         ac[i] = ac[i] + x[i] + c;
  26.         if (ac[i] > 1)
  27.         {
  28.             ac[i] = ac[i] % 2;
  29.             c = 1;
  30.         }
  31.         else
  32.             c = 0;
  33.     }
  34.  
  35. }
  36.  
  37. void ashr(int ac[], int qr[], int &qn, int qrn)
  38. {
  39.     int temp, i;
  40.  
  41.     temp = ac[0];
  42.     qn = qr[0];
  43.     cout << "\t\tashr\t\t";
  44.     for (i = 0; i < qrn - 1; i++)
  45.     {
  46.         ac[i] = ac[i + 1];
  47.         qr[i] = qr[i + 1];
  48.     }
  49.     qr[qrn - 1] = temp;
  50. }
  51.  
  52. void display(int ac[], int qr[], int qrn)
  53. {
  54.     int i;
  55.  
  56.     for (i = qrn - 1; i >= 0; i--)
  57.         cout << ac[i];
  58.     cout << " ";
  59.     for (i = qrn - 1; i >= 0; i--)
  60.         cout << qr[i];
  61.  
  62. }
  63.  
  64. int main(int argc, char **argv)
  65. {
  66.     int mt[10], br[10], qr[10], sc, ac[10] = { 0 };
  67.     int brn, qrn, i, qn, temp;
  68.     cout
  69.             << "\n--Enter the multiplicand and multipier in signed 2's complement form if negative--";
  70.  
  71.     cout << "\n Number of multiplicand bit=";
  72.     cin >> brn;
  73.     cout << "\nmultiplicand=";
  74.  
  75.     for (i = brn - 1; i >= 0; i--)
  76.         cin >> br[i]; //multiplicand
  77.  
  78.     for (i = brn - 1; i >= 0; i--)
  79.         mt[i] = br[i]; // copy multipier to temp array mt[]
  80.  
  81.     complement(mt, brn);
  82.  
  83.     cout << "\nNo. of multiplier bit=";
  84.     cin >> qrn;
  85.  
  86.     sc = qrn; //sequence counter
  87.  
  88.     cout << "Multiplier=";
  89.     for (i = qrn - 1; i >= 0; i--)
  90.         cin >> qr[i]; //multiplier
  91.  
  92.  
  93.     qn = 0;
  94.     temp = 0;
  95.  
  96.     cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n";
  97.     cout << "\t\t\tinitial\t\t";
  98.     display(ac, qr, qrn);
  99.     cout << "\t\t" << sc << "\n";
  100.  
  101.     while (sc != 0)
  102.     {
  103.         cout << qr[0] << "\t" << qn;
  104.         if ((qn + qr[0]) == 1)
  105.         {
  106.             if (temp == 0)
  107.             {
  108.                 add(ac, mt, qrn);
  109.                 cout << "\t\tsubtracting BR\t";
  110.                 for (i = qrn - 1; i >= 0; i--)
  111.                     cout << ac[i];
  112.                 temp = 1;
  113.             }
  114.             else if (temp == 1)
  115.             {
  116.                 add(ac, br, qrn);
  117.                 cout << "\t\tadding BR\t";
  118.                 for (i = qrn - 1; i >= 0; i--)
  119.                     cout << ac[i];
  120.                 temp = 0;
  121.             }
  122.             cout << "\n\t";
  123.             ashr(ac, qr, qn, qrn);
  124.         }
  125.         else if (qn - qr[0] == 0)
  126.             ashr(ac, qr, qn, qrn);
  127.  
  128.         display(ac, qr, qrn);
  129.         cout << "\t";
  130.  
  131.         sc--;
  132.         cout << "\t" << sc << "\n";
  133.     }
  134.     cout << "Result=";
  135.     display(ac, qr, qrn);
  136. }

Output:

$ g++ BoothsMultiplication.cpp
$ a.out
 
--Enter the multiplicand and multipier in signed 2's complement form if negative--
Number of multiplicand bit=5
Multiplicand=1 0 1 1 1
 
Number of multiplier bit=5
Multiplier=1 0 0 1 1
 
qn	q[n+1]		BR		AC	QR		sc
			initial		00000 10011		5
1	0		subtracting BR	01001
			ashr		00100 11001		4
1	1		ashr		00010 01100		3
0	1		adding BR	11001
			ashr		11100 10110		2
0	0		ashr		11110 01011		1
1	0		subtracting BR	00111
			ashr		00011 10101		0
 
Result=00011 10101

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.