El algoritmo de Booth es un algoritmo de multiplicación que multiplica dos números binarios con signo en notación de complemento a 2.
Booth usó calculadoras de escritorio que eran más rápidas para cambiar que para sumar y creó el algoritmo para aumentar su velocidad. El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras. Aquí está la implementación del algoritmo.
Ejemplos:
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
Algoritmo:
Ponga el multiplicando en BR y el multiplicador en QR
y luego el algoritmo funciona según las siguientes condiciones:
1. Si Q n y Q n+1 son iguales, es decir, 00 u 11, realice un cambio aritmético de 1 bit.
2. Si Q n Q n+1 = 10, haga A= A + BR y realice un desplazamiento aritmético de 1 bit.
3. Si Q n Q n+1 = 01 haga A= A – BR y realice un desplazamiento aritmético de 1 bit.
C++
// CPP code to implement booth's algorithm
#include <bits/stdc++.h>
using namespace std;
// function to perform adding in the accumulator
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
void 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 shift
void 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 operations
void 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 algo
void 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 code
int 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 algorithm
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];
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 accumulator
def 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 complement
def 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 shift
def 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 operations
def 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 algo
def 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 code
def 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 algorithm
using 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 accumulator
function 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 complement
function 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 shift
function 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 operations
function 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 algo
function 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 code
let mt = new Array(10).fill(0);
// Number of multiplicand bit
let brn = 4;
// multiplicand
let 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 bit
qrn = 4;
// sequence counter
let sc = qrn;
// multiplier
let 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
Producción :
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
Publicación traducida automáticamente
Artículo escrito por nickhilrawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA