Integer Division Design

Similar to manual long division, binary division involves iteratively determining quotient bits by seeing if the divisor can be subtracted from a portion of the dividend.

Let's divide a Dividend (N) by a Divisor (D) to get a Quotient (Q) and Remainder (R).

N=Q×D+R, where 0 ≤ R < D.

The process in binary long division involves:

1. Aligning the divisor with the most significant part of the dividend.
2. Attempting to subtract the divisor.
3. If successful (result is non-negative), the corresponding quotient bit is 1. The result becomes the new partial remainder.
4. If unsuccessful (result is negative), the corresponding quotient bit is 0. The partial remainder does not change (or is restored).
5. Shift the partial remainder left and repeat the process.

Sequential division algorithms are generally used in hardware, mimicking the manual process over several clock cycles.

Restoring Division Algorithm:

• Concept: This algorithm directly follows the manual long division procedure. In each step, it subtracts the divisor from the current partial remainder. If the subtraction results in a negative value (meaning the divisor was too large for that partial remainder), the original partial remainder is 'restored' (by adding the divisor back), and the quotient bit for that position is set to 0. If the subtraction results in a non-negative value, the result becomes the new partial remainder, and the quotient bit is 1.
• Structure: Requires:
• Registers: A register for the Dividend, a register for the Divisor, a register for the Quotient, and a register to hold the Remainder (often initialized with the Dividend).
• Adder/Subtractor: To perform the subtraction (and restoration if needed).
• Shifters: To shift the Remainder left and the Quotient bits into position.
• Control Unit: To manage the iterative steps.

Algorithm (Simplified for unsigned N-bit numbers):

1. Initialize the Remainder register (R) with the Dividend.
2. Initialize the Quotient register (Q) to 0.
3. Initialize the Divisor register (D) with the Divisor.
4. For N iterations (where N is the number of bits):
5. a. Left shift the Remainder register (R) by one bit.
6. b. Perform a 'trial subtraction': R_temp=R−D.
7. c. Check Result:
   • If R_temp≥0 (non-negative): This means the divisor fits. Set the least significant bit of the Quotient register (Q_0) to 1. Update the Remainder: R=R_temp.
   • If R_temp<0 (negative): This means the divisor doesn't fit. Set the least significant bit of the Quotient register (Q_0) to 0. Restore the Remainder: R=R+D (effectively undoing the trial subtraction).
8. d. Left shift the Quotient register (Q) by one bit to prepare for the next quotient bit.
9. After N iterations, the Quotient register holds the final quotient, and the Remainder register holds the final remainder.

Non-Restoring Division Algorithm:

• Concept: This algorithm improves upon restoring division by eliminating the 'restoring' step, making it faster. Instead of undoing a negative result, it uses the negative remainder directly in the next iteration, but changes the operation to addition instead of subtraction.

Algorithm (Simplified for unsigned N-bit numbers):

1. Initialize Remainder register (R) with Dividend, Quotient register (Q) to 0, Divisor register (D) with Divisor.
2. Initial Step (outside loop): Left shift R by one bit.
3. For N iterations:
4. a. Decide Operation:
   • If the Remainder (R) is currently negative (or was negative from the previous iteration, meaning the previous subtraction failed), ADD the Divisor (D) to the Remainder: R=R+D.
   • If the Remainder (R) is currently non-negative (or was non-negative from the previous iteration, meaning the previous subtraction succeeded), SUBTRACT the Divisor (D) from the Remainder: R=R−D.
5. b. Set Quotient Bit:
   • If the result of the operation in step (a) is non-negative: Set the LSB of the Quotient register (Q_0) to 1.
   • If the result of the operation in step (a) is negative: Set the LSB of the Quotient register (Q_0) to 0.
6. c. Left shift the Quotient register (Q) by one bit.
7. d. Prepare for next iteration: If this is not the last iteration, left shift the Remainder (R) by one bit.
8. Final Adjustment (after N iterations): If the final Remainder (R) is negative, add the Divisor (D) back to it one last time to make it positive. This one final restoration is sometimes needed.

Most hardware division units simplify the design by performing unsigned division internally. The signs of the final quotient and remainder are then determined based on the signs of the original dividend and divisor using predefined rules. This avoids the complexity of two's complement arithmetic within the core division algorithm.

Rules for Signs:

1. Quotient Sign:
2. If the original Dividend and Divisor have the same sign (both positive or both negative), the Quotient will be positive.
3. If the original Dividend and Divisor have different signs (one positive and one negative), the Quotient will be negative.
4. Remainder Sign:
5. The sign of the Remainder is typically defined to be the same as the sign of the original Dividend. This is a convention that simplifies number theory consistency.

Typical Implementation Strategy for Signed Division:

1. Convert to Absolute Values: Take the absolute (unsigned) value of both the Dividend and the Divisor. Store their original signs separately.
2. Perform Unsigned Division: Execute the unsigned division algorithm (either restoring or non-restoring) using these absolute values. This will yield an unsigned quotient and an unsigned remainder.
3. Adjust Quotient Sign: Apply the sign rule for the quotient. If the final quotient should be negative, convert the unsigned quotient result to its two's complement representation.
4. Adjust Remainder Sign: Apply the sign rule for the remainder. If the original Dividend was negative, convert the unsigned remainder result to its two's complement representation.