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. Here’s the implementation of the algorithm.
Examples:
Input : 0110, 0010
Output : qn q[n+1] AC QR sc(step count)
initial 0000 0010 4
0 0 rightShift 0000 0001 3
1 0 A = A - BR 1010
rightShift 1101 0000 2
0 1 A = A + BR 0011
rightShift 0001 1000 1
0 0 rightShift 0000 1100 0
Result=1100
Algorithm :
Put multiplicand in BR and multiplier in QR
and then the algorithm works as per the following conditions :
1. If Qn and Qn+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit.
2. If Qn Qn+1 = 01 do A= A + BR and perform arithmetic shift by 1 bit.
3. If Qn Qn+1 = 10 do A= A – BR and perform arithmetic shift by 1 bit.
C++
// CPP code to implement booth's algorithm#include <bits/stdc++.h>using namespace std;// function to perform adding in the accumulatorvoid add(int ac[], int x[], int qrn){ int i, c = 0; for (i = 0; i < qrn; i++) { // updating accumulator with A = A + BR ac[i] = ac[i] + x[i] + c; if (ac[i] > 1) { ac[i] = ac[i] % 2; c = 1; } else c = 0; }}// function to find the number's complementvoid complement(int a[], int n){ int i; int x[8] = {0}; x[0] = 1; for (i = 0; i < n; i++) { a[i] = (a[i] + 1) % 2; } add(a, x, n);}// function to perform right shiftvoid rightShift(int ac[], int qr[], int& qn, int qrn){ int temp, i; temp = ac[0]; qn = qr[0]; cout << "\t\trightShift\t"; for (i = 0; i < qrn - 1; i++) { ac[i] = ac[i + 1]; qr[i] = qr[i + 1]; } qr[qrn - 1] = temp;}// function to display operationsvoid display(int ac[], int qr[], int qrn){ int i; // accumulator content for (i = qrn - 1; i >= 0; i--) cout << ac[i]; cout << "\t"; // multiplier content for (i = qrn - 1; i >= 0; i--) cout << qr[i];}// Function to implement booth's algovoid boothAlgorithm(int br[], int qr[], int mt[], int qrn, int sc){ int qn = 0, ac[10] = { 0 }; int temp = 0; cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n"; cout << "\t\t\tinitial\t\t"; display(ac, qr, qrn); cout << "\t\t" << sc << "\n"; while (sc != 0) { cout << qr[0] << "\t" << qn; // SECOND CONDITION if ((qn + qr[0]) == 1) { if (temp == 0) { // subtract BR from accumulator add(ac, mt, qrn); cout << "\t\tA = A - BR\t"; for (int i = qrn - 1; i >= 0; i--) cout << ac[i]; temp = 1; } // THIRD CONDITION else if (temp == 1) { // add BR to accumulator add(ac, br, qrn); cout << "\t\tA = A + BR\t"; for (int i = qrn - 1; i >= 0; i--) cout << ac[i]; temp = 0; } cout << "\n\t"; rightShift(ac, qr, qn, qrn); } // FIRST CONDITION else if (qn - qr[0] == 0) rightShift(ac, qr, qn, qrn); display(ac, qr, qrn); cout << "\t"; // decrement counter sc--; cout << "\t" << sc << "\n"; }}// driver codeint main(int argc, char** arg){ int mt[10], sc; int brn, qrn; // Number of multiplicand bit brn = 4; // multiplicand int br[] = { 0, 1, 1, 0 }; // copy multiplier to temp array mt[] for (int i = brn - 1; i >= 0; i--) mt[i] = br[i]; reverse(br, br + brn); complement(mt, brn); // No. of multiplier bit qrn = 4; // sequence counter sc = qrn; // multiplier int qr[] = { 1, 0, 1, 0 }; reverse(qr, qr + qrn); boothAlgorithm(br, qr, mt, qrn, sc); cout << endl << "Result = "; for (int i = qrn - 1; i >= 0; i--) cout << qr[i];} |
Java
// Java code to implement booth's algorithmclass GFG{ // function to perform adding in the accumulator static void add(int ac[], int x[], int qrn) { int i, c = 0; for (i = 0; i < qrn; i++) { // updating accumulator with A = A + BR ac[i] = ac[i] + x[i] + c; if (ac[i] > 1) { ac[i] = ac[i] % 2; c = 1; } else { c = 0; } } } // function to find the number's complement static void complement(int a[], int n) { int i; int[] x = new int[8]; x[0] = 1; for (i = 0; i < n; i++) { a[i] = (a[i] + 1) % 2; } add(a, x, n); } // function ro perform right shift static void rightShift(int ac[], int qr[], int qn, int qrn) { int temp, i; temp = ac[0]; qn = qr[0]; System.out.print("\t\trightShift\t"); for (i = 0; i < qrn - 1; i++) { ac[i] = ac[i + 1]; qr[i] = qr[i + 1]; } qr[qrn - 1] = temp; } // function to display operations static void display(int ac[], int qr[], int qrn) { int i; // accumulator content for (i = qrn - 1; i >= 0; i--) { System.out.print(ac[i]); } System.out.print("\t"); // multiplier content for (i = qrn - 1; i >= 0; i--) { System.out.print(qr[i]); } } // Function to implement booth's algo static void boothAlgorithm(int br[], int qr[], int mt[], int qrn, int sc) { int qn = 0; int[] ac = new int[10]; int temp = 0; System.out.print("qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n"); System.out.print("\t\t\tinitial\t\t"); display(ac, qr, qrn); System.out.print("\t\t" + sc + "\n"); while (sc != 0) { System.out.print(qr[0] + "\t" + qn); // SECOND CONDITION if ((qn + qr[0]) == 1) { if (temp == 0) { // subtract BR from accumulator add(ac, mt, qrn); System.out.print("\t\tA = A - BR\t"); for (int i = qrn - 1; i >= 0; i--) { System.out.print(ac[i]); } temp = 1; } // THIRD CONDITION else if (temp == 1) { // add BR to accumulator add(ac, br, qrn); System.out.print("\t\tA = A + BR\t"); for (int i = qrn - 1; i >= 0; i--) { System.out.print(ac[i]); } temp = 0; } System.out.print("\n\t"); rightShift(ac, qr, qn, qrn); } // FIRST CONDITION else if (qn - qr[0] == 0) { rightShift(ac, qr, qn, qrn); } display(ac, qr, qrn); System.out.print("\t"); // decrement counter sc--; System.out.print("\t" + sc + "\n"); } } static void reverse(int a[]) { int i, k, n = a.length; int t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Driver code public static void main(String[] args) { int[] mt = new int[10]; int sc; int brn, qrn; // Number of multiplicand bit brn = 4; // multiplicand int br[] = {0, 1, 1, 0}; // copy multiplier to temp array mt[] for (int i = brn - 1; i >= 0; i--) { mt[i] = br[i]; } reverse(br); complement(mt, brn); // No. of multiplier bit qrn = 4; // sequence counter sc = qrn; // multiplier int qr[] = {1, 0, 1, 0}; reverse(qr); boothAlgorithm(br, qr, mt, qrn, sc); System.out.print("\n" + "Result = "); for (int i = qrn - 1; i >= 0; i--) { System.out.print(qr[i]); } }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 code to implement booth's algorithm# function to perform adding in the accumulatordef add(ac, x, qrn): c = 0 for i in range(qrn): # updating accumulator with A = A + BR ac[i] = ac[i] + x[i] + c; if (ac[i] > 1): ac[i] = ac[i] % 2 c = 1 else: c = 0# function to find the number's complementdef complement(a, n): x = [0] * 8 x[0] = 1 for i in range(n): a[i] = (a[i] + 1) % 2 add(a, x, n)# function to perform right shiftdef rightShift(ac, qr, qn, qrn): temp = ac[0] qn = qr[0] print("\t\trightShift\t", end = ""); for i in range(qrn - 1): ac[i] = ac[i + 1] qr[i] = qr[i + 1] qr[qrn - 1] = temp# function to display operationsdef display(ac, qr, qrn): # accumulator content for i in range(qrn - 1, -1, -1): print(ac[i], end = '') print("\t", end = '') # multiplier content for i in range(qrn - 1, -1, -1): print(qr[i], end = "")# Function to implement booth's algodef boothAlgorithm(br, qr, mt, qrn, sc): qn = 0 ac = [0] * 10 temp = 0 print("qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc") print("\t\t\tinitial\t\t", end = "") display(ac, qr, qrn) print("\t\t", sc, sep = "") while (sc != 0): print(qr[0], "\t", qn, sep = "", end = "") # SECOND CONDITION if ((qn + qr[0]) == 1): if (temp == 0): # subtract BR from accumulator add(ac, mt, qrn) print("\t\tA = A - BR\t", end = "") for i in range(qrn - 1, -1, -1): print(ac[i], end = "") temp = 1 # THIRD CONDITION elif (temp == 1): # add BR to accumulator add(ac, br, qrn) print("\t\tA = A + BR\t", end = "") for i in range(qrn - 1, -1, -1): print(ac[i], end = "") temp = 0 print("\n\t", end = "") rightShift(ac, qr, qn, qrn) # FIRST CONDITION elif (qn - qr[0] == 0): rightShift(ac, qr, qn, qrn) display(ac, qr, qrn) print("\t", end = "") # decrement counter sc -= 1 print("\t", sc, sep = "")# driver codedef main(): mt = [0] * 10 # Number of multiplicand bit brn = 4 # multiplicand br = [ 0, 1, 1, 0 ] # copy multiplier to temp array mt[] for i in range(brn - 1, -1, -1): mt[i] = br[i] br.reverse() complement(mt, brn) # No. of multiplier bit qrn = 4 # sequence counter sc = qrn # multiplier qr = [ 1, 0, 1, 0 ] qr.reverse() boothAlgorithm(br, qr, mt, qrn, sc) print("\nResult = ", end = "") for i in range(qrn - 1, -1, -1): print(qr[i], end = "") print() main()#This code is contributed by phasing17 |
C#
// C# code to implement// booth's algorithmusing System;class GFG{ // function to perform // adding in the accumulator static void add(int []ac, int []x, int qrn) { int i, c = 0; for (i = 0; i < qrn; i++) { // updating accumulator // with A = A + BR ac[i] = ac[i] + x[i] + c; if (ac[i] > 1) { ac[i] = ac[i] % 2; c = 1; } else c = 0; } } // function to find // the number's complement static void complement(int []a, int n) { int i; int []x = new int[8]; Array.Clear(x, 0, 8); x[0] = 1; for (i = 0; i < n; i++) { a[i] = (a[i] + 1) % 2; } add(a, x, n); } // function to perform // right shift static void rightShift(int []ac, int []qr, ref int qn, int qrn) { int temp, i; temp = ac[0]; qn = qr[0]; Console.Write("\t\trightShift\t"); for (i = 0; i < qrn - 1; i++) { ac[i] = ac[i + 1]; qr[i] = qr[i + 1]; } qr[qrn - 1] = temp; } // function to display // operations static void display(int []ac, int []qr, int qrn) { int i; // accumulator content for (i = qrn - 1; i >= 0; i--) Console.Write(ac[i]); Console.Write("\t"); // multiplier content for (i = qrn - 1; i >= 0; i--) Console.Write(qr[i]); } // Function to implement // booth's algo static void boothAlgorithm(int []br, int []qr, int []mt, int qrn, int sc) { int qn = 0; int []ac = new int[10]; Array.Clear(ac, 0, 10); int temp = 0; Console.Write("qn\tq[n + 1]\tBR\t" + "\tAC\tQR\t\tsc\n"); Console.Write("\t\t\tinitial\t\t"); display(ac, qr, qrn); Console.Write("\t\t" + sc + "\n"); while (sc != 0) { Console.Write(qr[0] + "\t" + qn); // SECOND CONDITION if ((qn + qr[0]) == 1) { if (temp == 0) { // subtract BR // from accumulator add(ac, mt, qrn); Console.Write("\t\tA = A - BR\t"); for (int i = qrn - 1; i >= 0; i--) Console.Write(ac[i]); temp = 1; } // THIRD CONDITION else if (temp == 1) { // add BR to accumulator add(ac, br, qrn); Console.Write("\t\tA = A + BR\t"); for (int i = qrn - 1; i >= 0; i--) Console.Write(ac[i]); temp = 0; } Console.Write("\n\t"); rightShift(ac, qr, ref qn, qrn); } // FIRST CONDITION else if (qn - qr[0] == 0) rightShift(ac, qr, ref qn, qrn); display(ac, qr, qrn); Console.Write("\t"); // decrement counter sc--; Console.Write("\t" + sc + "\n"); } } // Driver code static void Main() { int []mt = new int[10]; int sc, brn, qrn; // Number of // multiplicand bit brn = 4; // multiplicand int []br = new int[]{ 0, 1, 1, 0 }; // copy multiplier // to temp array mt[] for (int i = brn - 1; i >= 0; i--) mt[i] = br[i]; Array.Reverse(br); complement(mt, brn); // No. of // multiplier bit qrn = 4; // sequence // counter sc = qrn; // multiplier int []qr = new int[]{ 1, 0, 1, 0 }; Array.Reverse(qr); boothAlgorithm(br, qr, mt, qrn, sc); Console.WriteLine(); Console.Write("Result = "); for (int i = qrn - 1; i >= 0; i--) Console.Write(qr[i]); }}// This code is contributed by// Manish Shaw(manishshaw1) |
Javascript
//JavaScript code to implement booth's algorithm// function to perform adding in the accumulatorfunction add(ac, x, qrn){ let c = 0; for (let i = 0; i < qrn; i++) { // updating accumulator with A = A + BR ac[i] = ac[i] + x[i] + c; if (ac[i] > 1) { ac[i] = ac[i] % 2; c = 1; } else c = 0; }}// function to find the number's complementfunction complement(a, n){ let x = new Array(8).fill(0); x[0] = 1; for (let i = 0; i < n; i++) a[i] = (a[i] + 1) % 2; add(a, x, n);}// function to perform right shiftfunction rightShift(ac, qr, qn, qrn){ let temp = ac[0]; qn = qr[0]; process.stdout.write("\t\trightShift\t"); for (let i = 0; i < qrn - 1; i++) { ac[i] = ac[i + 1]; qr[i] = qr[i + 1]; } qr[qrn - 1] = temp;}// function to display operationsfunction display(ac, qr, qrn){ // accumulator content for (let i = qrn - 1; i > -1; i--) process.stdout.write(ac[i] + ""); process.stdout.write("\t"); // multiplier content for (i = qrn - 1; i > -1; i--) process.stdout.write(qr[i] + "");}// Function to implement booth's algofunction boothAlgorithm(br, qr, mt, qrn, sc){ let qn = 0; let ac = new Array(10).fill(0); let temp = 0; process.stdout.write("qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n"); process.stdout.write("\t\t\tinitial\t\t"); display(ac, qr, qrn); process.stdout.write("\t\t" + sc + "\n"); while (sc != 0) { process.stdout.write(qr[0] + "\t" + qn); // SECOND CONDITION if ((qn + qr[0]) == 1) { if (temp == 0) { // subtract BR from accumulator add(ac, mt, qrn); process.stdout.write("\t\tA = A - BR\t"); for (let i = qrn - 1; i > -1; i--) process.stdout.write(ac[i] + ""); temp = 1; } // THIRD CONDITION else if (temp == 1) { // add BR to accumulator add(ac, br, qrn); process.stdout.write("\t\tA = A + BR\t"); for (i = qrn - 1; i > -1; i--) process.stdout.write(ac[i] + ""); temp = 0; } process.stdout.write("\n\t"); rightShift(ac, qr, qn, qrn); } // FIRST CONDITION else if (qn - qr[0] == 0) rightShift(ac, qr, qn, qrn); display(ac, qr, qrn); process.stdout.write("\t"); // decrement counter sc -= 1; process.stdout.write("\t" + sc + "\n"); }}// driver codelet mt = new Array(10).fill(0); // Number of multiplicand bitlet brn = 4; // multiplicandlet br = [ 0, 1, 1, 0 ]; // copy multiplier to temp array mt[]for (let i = brn - 1; i > -1; i--) mt[i] = br[i]; br.reverse()complement(mt, brn)// No. of multiplier bitqrn = 4; // sequence counterlet sc = qrn; // multiplierlet qr = [ 1, 0, 1, 0 ];qr.reverse();boothAlgorithm(br, qr, mt, qrn, sc) process.stdout.write("\nResult = ");for (let i = qrn - 1; i > -1; i--) process.stdout.write(qr[i] + "");process.stdout.write("\n"); //This code is contributed by phasing17 |
Output :
qn q[n + 1] BR AC QR sc
initial 0000 1010 4
0 0 rightShift 0000 0101 3
1 0 A = A - BR 1010
rightShift 1101 0010 2
0 1 A = A + BR 0011
rightShift 0001 1001 1
1 0 A = A - BR 1011
rightShift 1101 1100 0
Result = 1100
Time Complexity: O(n)
Auxiliary Space: O(1)
