Booth's Algorithm Step Visualization

by Jyotismoy Kalita

Description

A small program written in Rust to display the Booth's Algorithm for multiplication step by step.

Cloning the repository

# Clone the repository
git clone https://github.com/JyotismoyKalita/booths-algorithm.git
cd booths-algo

Running Source file with cargo

You can compile and run your program using cargo:

Compiling

#debug version
#for release use --release
cargo build

Running

#debug version
#for release use --release
#Use "-h" for help.
#Use "-r VALUE" for specifying the Register Size
cargo run

Using the binary - booths-algorithm

Suppose in your current working directory you have saved the binary executable with the name booths-algorithm

Run the program

Running without -r flag would let you enter the register size during runtime.

./booths-algorithm

Run in Help mode

Display Help and other useful information

./booths-algorithm -h

Run with -r flag

Run with register size specified at compile time.

#here the Register size is specified as 4 bits
./booths-algorithm -r 4

Modules

Under the booth module we have 4 submodules

• io.rs: Contains functions for taking input and printing the values
• ops.rs: Contains Operations of Booth's Algorithm
• utils.rs: Contains other utility functions
• console.rs: Contains console functions

Structure

📦 booths-algotithm
├─ 📦 src
│  ├─ 📦 booth
│  │  ├─ 📄mod.rs
│  │  ├─ 📄io.rs
│  │  ├─ 📄ops.rs
│  │  ├─ 📄util.rs
│  │  └─ 📄console.rs
│  ├─ 📄main.rs
│  └─ 📄lib.rs
│  .gitignore
│  🔒Cargo.lock
├─ Cargo.toml
├─ 📖README.md
└─ 🪪LICENSE 

Help

FLAGS

-r X: Specify the register bit size where X is the specified size. 0 < X <= 16. If Register flag is not used when executing the program. The option to specify register will show during runtime.

-h: Use help.

DEFINITION OF STEPS

Initialization: Initial Value after loading up Multiplier and Multiplicand.

A <- A + M:   Values of Register A & M are added and put back into A register.

A <- A - M:   Values of Register M subtracted from A and put into A register.

ASR:       Arithmetic Shift Right. The MSB is retained while all other bits are shifted right starting from A to Q-1.

ALGORITHM

Action is determined by the Bits stored in 0th bit of Q and -1th bit of Q a.k.a Q-1. Here's the table for the actions -

Q	Q-1	Action
0	0	ASR
0	1	A <- A + M then ASR
1	0	A <- A - M then ASR
1	1	ASR

This Algorithm is repeated as many times as there are Bits in the Registers.

E.g. If Register size if 4, the Algorithm is repeated 4 times.