Booths Division Algorithm

This program implements Booth's algorithm to perform division of two numbers. The algorithm is used to perform multiplication or division of binary numbers.

Prerequisites

• Python 3.10.2 or above
• Binary.py module (included)

How to use

Run the program.

• Enter the number of bits for the registers.
• Enter the dividend and divisor values in the corresponding binary or 2's complement form.
• The program will output the intermediate steps for each cycle and the final quotient and remainder.

Inputs

The program accepts the following inputs:

• no_bits: Number of bits for the registers.
• dividend: Dividend value in binary or 2's complement form.
• divisor: Divisor value in binary or 2's complement form.

Outputs

The program outputs the following:

• Intermediate steps for each cycle.
• Final quotient and remainder.

Example

Input:

Enter the number of bits : 12
Enter the Values in the corresponding binary or 2's complement form
Enter the divident  : 110101101
Enter the divisor : 1101

Output:

     A            Q            M

000000000000 000110101101 000000001101   Initial Values

000000000000 001101011010 000000001101   Shift left A, Q            ─┐
111111110011 001101011010 000000001101   A <- A - M                  ├── Cycle 1
000000000000 001101011010 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000000 011010110100 000000001101   Shift left A, Q            ─┐
111111110011 011010110100 000000001101   A <- A - M                  ├── Cycle 2
000000000000 011010110100 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000000 110101101000 000000001101   Shift left A, Q            ─┐
111111110011 110101101000 000000001101   A <- A - M                  ├── Cycle 3
000000000000 110101101000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000001 101011010000 000000001101   Shift left A, Q            ─┐
111111110100 101011010000 000000001101   A <- A - M                  ├── Cycle 4
000000000001 101011010000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000011 010110100000 000000001101   Shift left A, Q            ─┐
111111110110 010110100000 000000001101   A <- A - M                  ├── Cycle 5
000000000011 010110100000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000110 101101000000 000000001101   Shift left A, Q            ─┐
111111111001 101101000000 000000001101   A <- A - M                  ├── Cycle 6
000000000110 101101000000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000001101 011010000000 000000001101   Shift left A, Q            ─┐
000000000000 011010000000 000000001101   A <- A - M                  ├── Cycle 7
000000000000 011010000001 000000001101   Set Q[0] = 1               ─┘

000000000000 110100000010 000000001101   Shift left A, Q            ─┐
111111110011 110100000010 000000001101   A <- A - M                  ├── Cycle 8
000000000000 110100000010 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000001 101000000100 000000001101   Shift left A, Q            ─┐
111111110100 101000000100 000000001101   A <- A - M                  ├── Cycle 9
000000000001 101000000100 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000011 010000001000 000000001101   Shift left A, Q            ─┐
111111110110 010000001000 000000001101   A <- A - M                  ├── Cycle 10
000000000011 010000001000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000000110 100000010000 000000001101   Shift left A, Q            ─┐
111111111001 100000010000 000000001101   A <- A - M                  ├── Cycle 11
000000000110 100000010000 000000001101   Restore A, Set Q[0] = 0    ─┘

000000001101 000000100000 000000001101   Shift left A, Q            ─┐
000000000000 000000100000 000000001101   A <- A - M                  ├── Cycle 12
000000000000 000000100001 000000001101   Set Q[0] = 1               ─┘

Quotient : 000000100001         (33)
Remainder : 000000000000        (0)

Credits

This program was developed by Valerian Coelho. It uses the Binary Library, which were developed by the same author.