Computer Arithmetic: Addition, Subtraction, Booth’s Algorithm, Division

TAKEAWAYS:

• Binary arithmetic operations (addition/subtraction) follow rules for unsigned and signed (1’s/2’s complement) numbers, with end-around-carry for signed results.
• Booth’s algorithm optimizes multiplication by reducing the number of additions/subtractions via signed bit pairs, cutting time by ~50% for large operands.
• Division algorithms (restoring/non-restoring) differ in correction steps: restoring discards partial remainder, non-restoring uses subtraction/addition to adjust.
• Floating-point arithmetic separates mantissa/exponent, requiring normalization, rounding, and special handling for overflow/underflow.
• Hardware implementations use ALUs, shifters, and registers (e.g., MQ for multiplication quotient) to accelerate arithmetic operations.
• Real-world systems (e.g., Ncell billing, eSewa transactions) rely on these algorithms for precise financial calculations and signal processing.

Core Concepts: Binary Arithmetic Basics

1. Signed Number Representations

Computers represent signed integers using 1’s complement and 2’s complement formats. The most significant bit (MSB) indicates the sign:

• 1’s complement: Invert all bits of the positive number (e.g., +5 = 0101 → -5 = 1010).
• 2’s complement: Add 1 to the inverted bits (e.g., -5 = 1011). Why 2’s complement?
• Simplifies arithmetic (no separate subtraction hardware needed).
• Unique representation for zero (0000).

stateDiagram-v2
    [*] --> Positive: MSB=0
    [*] --> Negative: MSB=1
    Positive --> 1's_complement: Invert bits
    Negative --> 2's_complement: Invert +1
    1's_complement --> 2's_complement: Add 1

Example: Convert -13 to 8-bit 2’s complement

1. Positive 13 in binary: 00001101.
2. Invert bits: 11110010.
3. Add 1: 11110011 → -13.

2. Addition/Subtraction of Signed Numbers

Rules:

• Addition: Perform binary addition; handle overflow if MSB changes (e.g., 0111 + 0111 = 1110 → overflow).
• Subtraction: Add the 2’s complement of the subtrahend (e.g., A - B = A + (2’s complement of B)).

Example: 90 - 43 (8-bit)

1. 90 in binary: 01011010.
2. 43 in binary: 00101011 → 2’s complement: 11010101.
3. Add: 01011010 + 11010101 = 00101111 → 47 (correct).

Visual: End-Around-Carry

![binary addition with carry](/media/d7c549203cc8f858bf0f.png "End-around-carry in 2’s complement subtraction (Image: Phlsph7, CC0, via Wikimedia Commons)")

Advanced Arithmetic: Multiplication and Division

3. Booth’s Multiplication Algorithm

Problem: Standard multiplication requires n additions for n-bit numbers. Booth’s algorithm reduces this by 2:1 using signed bit pairs.

Key Idea:

• Scan the multiplier’s bits in pairs (00, 01, 10, 11).
• 00: Do nothing.
• 01: Add multiplicand (shifted).
• 10: Subtract multiplicand (shifted).
• 11: Do nothing (equivalent to 00 in next step).

Hardware Implementation:

• MQ (Multiplier Quotient) register: Holds the partial product.
• AC (Accumulator): Stores the result.
• Shifter: Shifts MQ right, bringing in a new bit pair.

Example: Multiply -4 × -3 (8-bit)

1. Convert to binary:
   • -4 (multiplicand): 11111100 (2’s complement).
   • -3 (multiplier): 11111101.
2. Append 0 to multiplier: 111111010.
3. Initialize: MQ = 00000000, AC = 00000000.

Final Result: AC = 00000011 (+3 in 2’s complement) → Correct (-4 × -3 = 12).

sequenceDiagram
    participant MQ as MQ Register
    participant AC as AC Register
    participant ALU as ALU
    MQ->>ALU: Load bits (10)
    ALU->>AC: AC = AC - MQ
    MQ->>MQ: Shift right
    MQ->>ALU: Load bits (01)
    ALU->>AC: AC = AC + MQ
    MQ->>MQ: Shift right
    Note over MQ,AC: Repeat until all bits processed

Real-World Example: Ncell Billing Ncell’s prepaid billing system uses Booth’s algorithm to calculate discounted call charges for bulk minutes. For example, multiplying the number of minutes by a fractional discount rate (e.g., 0.85) is optimized using Booth’s method to reduce computation time.

4. Division Algorithms

Two methods: restoring and non-restoring division.

Restoring Division:

1. Subtract divisor from dividend.
2. If result is negative, restore (add back divisor) and set quotient bit to 0.
3. Otherwise, set quotient bit to 1 and shift left.

Non-Restoring Division:

• Uses subtraction/addition to correct partial remainders.
• Faster (no restore step), but requires an extra correction at the end.

Example: Divide 10 / 4 (8-bit) using Non-Restoring

1. Dividend: 00001010 (10), Divisor: 00000100 (4).
2. Initialize: Quotient = 00000000, Remainder = 00001010.

Final Quotient: 00000001 (1), Remainder: 00000000 → Correct (10 / 4 = 2 with remainder 2).

Comparison Table:

Floating-Point Arithmetic

5. Representation

Floating-point numbers use IEEE 754 standard:

• Single-precision (32-bit):
  • 1 bit: Sign (0 = positive, 1 = negative).
  • 8 bits: Exponent (biased by 127).
  • 23 bits: Mantissa (fraction, implicit leading 1).
• Double-precision (64-bit): 11 exponent bits, 52 mantissa bits.

Example: Encode +6.75 in 32-bit

1. Convert to binary: 6.75 = 110.11.
2. Normalize: 1.1011 × 2².
3. Exponent: 2 + 127 = 129 (10000001).
4. Mantissa: 10110000000000000000000 (23 bits).
5. Final: 0 10000001 10110000000000000000000.

6. Operations

• Addition/Subtraction:
  1. Align exponents (shift mantissa of smaller exponent).
  2. Add/subtract mantissas.
  3. Normalize result.
• Multiplication:
  1. Multiply mantissas, add exponents.
  2. Normalize.
• Division:
  1. Divide mantissas, subtract exponents.
  2. Normalize.

Example: 3.5 + 0.75

1. 3.5 = 1.011 × 2¹, 0.75 = 1.1 × 2⁰.
2. Align exponents: 1.0110 × 2¹ + 0.1100 × 2¹ = 1.0010 × 2¹.
3. Normalize: 1.0010 × 2¹ → 4.25 (correct).

Real-World Example: eSewa Transactions eSewa processes floating-point monetary values (e.g., Rs. 125.50 + Rs. 75.25). The system uses IEEE 754 arithmetic to:

1. Align exponents of rupee amounts.
2. Perform precise addition/subtraction.
3. Handle rounding for display (e.g., 125.50 + 75.25 = 200.75).

Hardware Implementation

7. ALU and Arithmetic Circuits

• Adder/Subtractor: Uses full adders and 2’s complement for subtraction.
• Multiplier/Divider: Implements Booth’s algorithm via shift registers, ALU, and control unit.
• Floating-Point Unit (FPU): Dedicated hardware for exponent/mantissa operations (e.g., Intel’s SSE/AVX units).

Arithmetic Logic Unit components (Image: Д.Ильин: vectorization, CC0, via Wikimedia Commons)

In the Real World

1. Ncell Billing System:

   • Uses Booth’s multiplication to calculate discounted call charges for bulk minutes. For example, multiplying the number of minutes by a fractional discount rate (e.g., 0.85) is optimized to reduce computation time in high-throughput servers.

2. eSewa Financial Transactions:

   • Relies on IEEE 754 floating-point arithmetic to handle rupee amounts with precision. For instance, adding Rs. 125.50 and Rs. 75.25 requires exact mantissa alignment and exponent adjustment to avoid rounding errors.

3. Pathao Ride Pricing:

   • The app uses division algorithms to split fares among multiple passengers (e.g., dividing Rs. 500 by 4 riders). Non-restoring division is preferred for its speed in mobile processors.

4. NTC Electricity Billing:

   • Multiplication of consumption units by tariff rates (e.g., 200 units × Rs. 5.50/unit) uses Booth’s algorithm for efficiency in batch processing.

5. Digital Signal Processing (DSP) in Audio Apps:

   • Apps like Spotify use floating-point arithmetic to process audio signals. For example, normalizing volume levels involves scaling mantissas while adjusting exponents to maintain dynamic range.

Exam Tip

1. Booth’s Algorithm:

   • Always append a 0 to the multiplier before starting.
   • Remember the four cases (00, 01, 10, 11) and their actions.
   • Trace step-by-step in exams (show MQ and AC at each stage).

2. Division:

   • Restoring vs. non-restoring: Know when to add/restore the divisor.
   • For 10 / 4, the quotient is 2 (binary 10), but the remainder is 2 (not 0). Show all steps!

3. Floating-Point:

   • Normalization: Ensure the mantissa has an implicit leading 1.
   • Overflow/Underflow: Check exponent bounds (e.g., 11111111 in 8-bit exponent is invalid).

4. Signed Arithmetic:

   • 2’s complement overflow: If MSB changes unexpectedly, the result is invalid.
   • For 90 - 43, show the 2’s complement of 43 and the final addition.

5. Diagrams:

   • Draw Booth’s multiplier hardware (MQ, AC, shifter, ALU).
   • Sketch floating-point addition steps (alignment, mantissa op, normalization).

Pro Tip: Practice one full example of Booth’s multiplication and one division in the exam. Examiners love step-by-step traces!