Write Booth's algorithm. Also explain floating point arithmetic operation.

Introduction

Booth's algorithm and floating point arithmetic operations are two fundamental concepts in computer organization and architecture. Booth's algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. On the other hand, floating point arithmetic operations involve the addition, subtraction, multiplication, and division of floating point numbers, which are numbers that have a decimal point.

Booth's Algorithm

Definition and Purpose

Booth's algorithm, named after Andrew Donald Booth, is a method for multiplying binary integers. The algorithm is efficient in terms of the number of addition/subtraction operations required. It handles positive and negative multipliers by using two's complement representation.

Step by Step Process of Booth's Algorithm

Initialization

The first step in Booth's algorithm is to initialize the variables. We need two registers, A and Q, to hold the multiplicand and multiplier respectively. We also need a register Q-1 to hold the rightmost bit of Q from the previous step, and a register M to hold the multiplicand.

Looping Through the Bits

The next step is to loop through the bits of the multiplier (Q). For each bit, we check the current bit and the previous bit (Q and Q-1).

Checking the Conditions and Performing Operations

If the current bit and the previous bit are the same (00 or 11), we do nothing. If the current bit is 0 and the previous bit is 1 (01), we add the multiplicand to A. If the current bit is 1 and the previous bit is 0 (10), we subtract the multiplicand from A. After each operation, we perform an arithmetic right shift on the registers A and Q.

Final Result

After looping through all the bits of the multiplier, the product of the multiplication is stored in the registers A and Q.

Formulas Used in Booth's Algorithm

The main operations in Booth's algorithm are addition and subtraction. The formulas used are:

• Addition: A = A + M
• Subtraction: A = A - M

Example of Booth's Algorithm

Let's multiply 3 (011 in binary) and 2 (010 in binary) using Booth's algorithm.

1. Initialization: A = 000, Q = 010, Q-1 = 0, M = 011
2. First iteration (Q0Q-1 = 00): Do nothing, right shift AQ: A = 000, Q = 001, Q-1 = 0
3. Second iteration (Q0Q-1 = 10): A = A - M = 111, right shift AQ: A = 111, Q = 100, Q-1 = 1
4. Third iteration (Q0Q-1 = 01): A = A + M = 010, right shift AQ: A = 001, Q = 110, Q-1 = 0

The final result is AQ = 001110, which is 6 in decimal, the product of 3 and 2.

Writing a Program for Booth's Algorithm

Here is a Python program that implements Booth's algorithm:

def booth(multiplicand, multiplier):
    A = 0
    Q = multiplier
    Q_minus_1 = 0
    M = multiplicand
    for _ in range(len(bin(multiplier))-2):  # -2 to exclude '0b' prefix
        if Q & 1 == Q_minus_1:  # Q0Q-1 = 00 or 11
            pass
        elif Q & 1 == 1:  # Q0Q-1 = 10
            A -= M
        else:  # Q0Q-1 = 01
            A += M
        A, Q = A >> 1, (A << (len(bin(multiplier))-3) & 0b100 | Q >> 1)  # -3 to exclude '0b' prefix and Q0
        Q_minus_1 = Q & 1
    return (A << (len(bin(multiplier))-2) | Q)  # -2 to exclude '0b' prefix

print(booth(3, 2))  # Outputs: 6

Floating Point Arithmetic Operation

Definition and Purpose

Floating point arithmetic operations involve the addition, subtraction, multiplication, and division of floating point numbers. These numbers are represented in a computer as a set of bits with three parts: the sign, the exponent, and the fraction (also known as the mantissa).

Step by Step Process of Floating Point Arithmetic Operation

Representation of Numbers in Floating Point

Floating point numbers are represented in a computer using the IEEE 754 standard. The standard defines the bit layout for single-precision (32-bit) and double-precision (64-bit) floating point numbers.

Performing Addition, Subtraction, Multiplication, and Division

The steps to perform floating point arithmetic operations are as follows:

• Addition/Subtraction: Align the numbers by the exponent, perform the operation on the mantissas, and normalize the result.
• Multiplication/Division: Add/Subtract the exponents, perform the operation on the mantissas, and normalize the result.

Rounding and Normalization

After each operation, the result is rounded to the nearest representable number and normalized (the mantissa is adjusted so that it is always less than 1).

Formulas Used in Floating Point Arithmetic Operation

The formulas used in floating point arithmetic operations are:

• Addition/Subtraction: (mantissa1 * 2^exponent1) ± (mantissa2 * 2^exponent2)
• Multiplication/Division: (mantissa1 * mantissa2) * 2^(exponent1 ± exponent2)

Example of Floating Point Arithmetic Operation

Let's add 1.5 (1.1 in binary) and 2.5 (10.1 in binary) using floating point arithmetic operation.

1. Representation: 1.5 = 1.1 * 2^0, 2.5 = 1.01 * 2^1
2. Alignment: 1.5 = 0.11 * 2^1
3. Addition: 0.11 + 1.01 = 1.12
4. Normalization: 1.12 * 2^1 = 1.1 * 2^2

The final result is 1.1 * 2^2, which is 4 in decimal, the sum of 1.5 and 2.5.

Writing a Program for Floating Point Arithmetic Operation

Here is a Python program that performs floating point addition:

def float_add(a, b):
    return a + b

print(float_add(1.5, 2.5))  # Outputs: 4.0

Comparison between Booth's Algorithm and Floating Point Arithmetic Operation

Conclusion

Booth's algorithm and floating point arithmetic operations are essential in computer organization and architecture. Booth's algorithm allows efficient multiplication of binary integers, while floating point arithmetic operations enable the manipulation of real numbers. Understanding these concepts is crucial for designing and implementing computer systems.

Summary

Booth's algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. It is efficient in terms of the number of addition/subtraction operations required. Floating point arithmetic operations involve the addition, subtraction, multiplication, and division of floating point numbers, which are numbers that have a decimal point.

Analogy

Booth's algorithm is like a specialized calculator that efficiently multiplies binary numbers, while floating point arithmetic operations are like performing calculations with decimal numbers.