Experiment 07 – Restoring division
Learning Objectives: To implement and trace the restoring division algorithm cycle-by-cycle for
signed and unsigned binary integers.
Tools/Software Required: Verilog Online Compiler (Python 3)
Theory:
1. Introduction
Binary division is a fundamental arithmetic operation used in digital systems and computer
architecture. The restoring division algorithm is one of the classical methods used to perform binary
division using shift-and-subtract operations.
It is called “restoring” because, after each subtraction step, if the result becomes negative, the partial
remainder is restored by adding back the divisor before proceeding to the next bit.
2. Principle
In binary division, the process mimics long division in base 2:
• We align the divisor (M) with the dividend (Q),
• Use a separate accumulator (A) to hold partial remainders,
• Repeatedly shift left and subtract the divisor,
• Restore the value if subtraction leads to a negative remainder,
• Build up the quotient (Q) bit-by-bit.
Registers used:
• A (Accumulator) → (n+1) bits (stores remainder/partial result)
• Q (Dividend / Quotient Register) → n bits
• M (Divisor) → n bits
3. Step-by-Step Explanation of Unsigned Restoring Division
Let us understand how the algorithm works for positive (unsigned) binary numbers.
Step 1: Initialization
• Load the dividend in register Q.
• Load the divisor in register M.
• Set register A (the accumulator) to zero.
Step 2: Repeat the following steps for ‘n’ cycles,
where n is the number of bits in the dividend:
1. Left Shift
o Combine A and Q together and shift them left by one bit.
o This step brings down the next bit of the dividend into the accumulator.
2. Subtraction
o Subtract the divisor (M) from the accumulator (A).
3. Check the Sign of A
o If the value in A is positive or zero,
▪ The subtraction was successful.
▪ Set the least significant bit (last bit) of Q to 1.
o If the value in A is negative,
▪ The subtraction failed.
▪ Restore the old value of A by adding M back to it.
▪ Set the last bit of Q to 0.
4. Continue this process for all bits of Q.
Step 3: Final Result
• After completing all n steps,
o The quotient is stored in register Q.
o The remainder is stored in register A.
4. Signed Restoring Division
The unsigned restoring division works only for positive numbers.
For signed numbers (positive or negative), we use an additional step.
Steps for Signed Division:
1. Take the absolute values of both the dividend and divisor.
2. Apply the unsigned restoring division algorithm on them.
3. After obtaining the quotient and remainder:
o The sign of the quotient is determined by the rule:
▪ If both dividend and divisor have the same sign → quotient is positive.
▪ If they have different signs → quotient is negative.
o The remainder takes the same sign as the dividend.
5. Advantages
• The algorithm is simple and easy to implement.
• It follows a systematic and predictable sequence of steps.
• Suitable for hardware design using shift registers and adders.
• Works correctly for both signed and unsigned binary numbers.
6. Disadvantages
• The restore step (adding the divisor back when subtraction fails)
makes the algorithm slower compared to more advanced division algorithms.
• It needs an extra bit in the accumulator to handle negative results.
• Not very efficient for large numbers.
7. Applications
• Used in ALUs (Arithmetic Logic Units) in early computer processors.
• Helps understand the basic working of binary division circuits.
• Forms the foundation for modern algorithms like Non-Restoring and SRT Division.
Program:
def mask(bits: int) -> int:
return (1 << bits) - 1
def to_signed(x: int, bits: int) -> int:
"""Interpret x (masked) as signed two's-complement with 'bits' bits."""
x &= mask(bits)
if x & (1 << (bits - 1)):
return x - (1 << bits)
return x
def from_signed(x: int, bits: int) -> int:
"""Encode signed integer x into two's-complement representation masked to bits."""
return x & mask(bits)
def bin_str(x: int, bits: int) -> str:
return format(x & mask(bits), '0{}b'.format(bits))
def restoring_division_unsigned(dividend: int, divisor: int, n: int) -> Tuple[int, int, List[dict]]:
"""
Perform restoring division for UNSIGNED integers.
dividend, divisor: non-negative ints fitting in n bits.
Returns (quotient, remainder, trace_list).
A is (n+1)-bit register used in trace.
"""
if divisor == 0:
raise ZeroDivisionError("Divisor cannot be zero.")
# Masks
mask_q = mask(n)
mask_a = mask(n + 1)
# Check fit
if dividend < 0 or divisor < 0:
raise ValueError("This function is unsigned-only. Use the signed wrapper.")
if dividend > mask_q:
raise ValueError(f"Dividend {dividend} doesn't fit in {n} bits.")
if divisor > mask_q:
raise ValueError(f"Divisor {divisor} doesn't fit in {n} bits.")
A = 0 # n+1 bits
Q = dividend & mask_q
M = divisor & mask_q
trace = []
for step in range(1, n + 1):
# Left shift [A,Q] by 1: A <- (A<<1) | MSB(Q); Q <- (Q<<1) & mask_q
q_msb = (Q >> (n - 1)) & 1
A = ((A << 1) | q_msb) & mask_a
Q = ((Q << 1) & mask_q)
# A = A - M (use signed interpretation of A for negativity check)
A_signed_before = to_signed(A, n + 1)
# For subtraction, represent M in n+1 bits (non-negative)
A_after_sub = (A_signed_before - M) & mask_a
A = A_after_sub
A_signed_after = to_signed(A, n + 1)
if A_signed_after < 0:
# Restore: A = A + M, Q0 = 0
# Q LSB already zero by shift; ensure explicitly:
Q = Q & (~1)
# Add back M (as positive) into A (treat A as signed then re-encode)
A = (A_signed_after + M) & mask_a # restore (A + M)
op = "A-M < 0 -> restore (Q0=0)"
else:
# Set Q0 = 1 (successful subtraction)
Q=Q|1
op = "A-M >= 0 -> accept (Q0=1)"
[Link]({
'step': step,
'op': op,
'A_bin': bin_str(A, n + 1),
'Q_bin': bin_str(Q, n),
'A_dec_signed': to_signed(A, n + 1),
'Q_dec_unsigned': Q
})
quotient = Q & mask_q
remainder = A & mask_a
# remainder should be < divisor; as unsigned ints
return quotient, remainder, trace
def restoring_division_signed(dividend: int, divisor: int, n: int) -> Tuple[int, int, List[dict]]:
"""
Signed restoring division wrapper.
Returns (quotient_signed, remainder_signed, trace)
- quotient is truncated toward zero (sign = sign(dividend) XOR sign(divisor))
- remainder has same sign as dividend such that: dividend = divisor*quotient + remainder
"""
if divisor == 0:
raise ZeroDivisionError("Divisor cannot be zero.")
# Record signs
sign_dividend = 1 if dividend < 0 else 0
sign_divisor = 1 if divisor < 0 else 0
sign_q = sign_dividend ^ sign_divisor
abs_dividend = abs(dividend)
abs_divisor = abs(divisor)
# For safety, ensure abs values fit in n bits
if abs_dividend > mask(n):
raise ValueError(f"Absolute dividend {abs_dividend} doesn't fit in {n} bits.")
if abs_divisor > mask(n):
raise ValueError(f"Absolute divisor {abs_divisor} doesn't fit in {n} bits.")
q_unsigned, r_unsigned, trace = restoring_division_unsigned(abs_dividend, abs_divisor, n)
# apply signs
quotient_signed = -q_unsigned if sign_q else q_unsigned
# remainder sign same as dividend: if dividend < 0, remainder = -r_unsigned
remainder_signed = -r_unsigned if sign_dividend else r_unsigned
# Add meta-info to trace first row for signed wrapper
wrapper_info = {
'note': 'Signed-mode wrapper used; algorithm ran on absolute values.'
}
# Prepend or append note
trace = [wrapper_info] + trace
return quotient_signed, remainder_signed, trace
def pretty_run(dividend: int, divisor: int, n: int, signed: bool = False):
print(f"\nRestoring Division: dividend = {dividend}, divisor = {divisor}, n = {n}, signed =
{signed}")
if signed:
q, r, trace = restoring_division_signed(dividend, divisor, n)
else:
q, r, trace = restoring_division_unsigned(dividend, divisor, n)
# Pretty print trace
if trace and isinstance(trace[0], dict) and 'note' in trace[0]:
print("NOTE:", trace[0]['note'])
trace_rows = trace[1:]
else:
trace_rows = trace
header = f"{'Step':>4} | {'Operation':>28} | {'A (bin)':>{n+3}} | {'Q (bin)':>{n+1}} |
{'A(signed)':>10} | {'Q(unsigned)':>12}"
print(header)
print("-" * len(header))
for row in trace_rows:
print(f"{row['step']:>4} | {row['op']:<28} | {row['A_bin']:>{n+3}} | {row['Q_bin']:>{n+1}} |
{row['A_dec_signed']:>10} | {row['Q_dec_unsigned']:>12}")
print("-" * len(header))
if signed:
print(f"Final (signed) quotient = {q}, remainder = {r}")
else:
print(f"Final (unsigned) quotient = {q}, remainder = {r} (A register)")
if _name_ == "_main_":
# Example tests
# 1) Unsigned 13 / 3 with n=4 -> quotient 4, remainder 1
pretty_run(13, 3, n=4, signed=False)
# 2) Unsigned 15 / 4 with n=4 -> quotient 3, remainder 3
pretty_run(15, 4, n=4, signed=False)
# 3) Signed example: -13 / 3 -> quotient -4, remainder -1 (use n=5 to fit -13)
pretty_run(-13, 3, n=5, signed=True)
# 4) Signed example: 13 / -3 -> quotient -4, remainder 1 (use n=5)
pretty_run(13, -3, n=5, signed=True)
# 5) Edge case: divisor > dividend
pretty_run(3, 5, n=4, signed=False)
Learning Outcomes: Students will able to
LO7.1 Understand the working principle of the restoring division algorithm in binary arithmetic.
LO7.2 Learn to implement the algorithm for both signed and unsigned binary numbers.
LO7.3 Analyze each cycle of the algorithm to trace quotient and remainder formation.
Course Outcome: After the completion of course Students will be able to apply arithmetic algorithms
like restoring division to perform efficient binary computations in digital systems.