A New Variant of the Proof of Correctness of the Non-Restoring Division Method
Abstract Generated abstract
This paper revisits the proof of correctness for the non-restoring division method used in digital arithmetic units, especially in implementations where relative shifting is achieved by shifting the divisor register. It contrasts division with explicit remainder restoration and division without explicit restoration, then reformulates the standard justification of the latter through a direct transformation of the negative remainder produced by the restoring method. The argument shows that, when a negative remainder occurs, the next required remainder can be obtained by adding the divisor shifted for the next cycle, which is equivalent to restoration followed by the next subtraction. The paper therefore clarifies the logical basis of the method and suggests more precise terminology: division with explicit restoration and division without explicit restoration of the remainder.
Full Text
A NEW VERSION OF THE PROOF OF CORRECTNESS OF THE NON-RESTORING DIVISION METHOD
A. V. TRIKHANOV
(Presented by the scientific seminar of the Department of Computer Engineering)
It is known [1–3] that there are two basic methods of division:
1) division with restoration of the remainder (the first method),
2) division without restoration of the remainder (the second method).
For their implementation an adder is used into which, before division, the dividend \(D\), the quotient register Q, and the divisor register \(d\) are entered. The relative shift of the positive remainder (the dividend in the first cycle) and of the divisor is created by shifting either in the adder or in the divisor register. The latter is more widely used.
A division device, on the basis of \(D\) and \(d\), forms the quotient digits Q. If the sign and the integer part of the quotient are not taken into account, then one may assume that
\[ \mathrm{Q}=0,r_1r_2\ldots r_i\ldots r_n, \tag{1} \]
where \(r_i\) is the digit of the \(i\)-th place of the quotient.
In accordance with (1),
\[ D=dr_1 2^{-1}+dr_2 2^{-2}+\cdots+dr_i 2^{-i}+\cdots+dr_n 2^{-n}. \tag{2} \]
It follows from (2) that the digit \(r_1\) can be determined on the basis of the remainder \(Q_1=D-d\cdot 2^{-1}\) by the following algorithm:
\[ \text{if } Q_1\ge 0,\ \text{then } r_1=1, \tag{3} \]
\[ \text{if } Q_1<0,\ \text{then } r_1=0. \tag{4} \]
In the case of (4), restoration of the preceding positive remainder (the dividend in the first cycle) must then be performed:
\[ Q_1+d\cdot 2^{-1}=D-d\cdot 2^{-1}+d\cdot 2^{-1}=D. \tag{5} \]
In the \(i\)-th cycle the following expressions may be used:
\[ Q_i=Q_{i-1}-d\cdot 2^{-i}, \tag{6} \]
\[ \text{if }\quad Q_i\ge 0,\ \text{then } r_i=1, \tag{7} \]
\[ \text{if }\quad Q_i<0,\ \text{then } r_i=0, \tag{8} \]
\[ \text{if }\quad Q_i<0,\ \text{then } Q_i+d\cdot 2^{-i}=Q_{i-1}. \tag{9} \]
Expressions (6–8) constitute the basis of the first division method. A distinctive feature of the first method is the use of expression (9).
The second method of division, when \(Q_i<0\), before obtaining the \((i+1)\)-st digit, excludes the restoration of the last positive remainder \(Q_{i-1}\) in accordance with (9). Instead, the divisor, additionally shifted \(\bigl(d\cdot 2^{-(i+1)}\bigr)\), is added to \(Q_i\). The well-known proof of the correctness of the second division method, presented in [1] for a shift in the adder, as applied to a shift of the divisor, could be set out as follows:
Suppose that \(Q_i<0\). According to the procedure adopted in this method, we obtain the value \(d\cdot 2^{-(i+1)}\) and add it to the remainder; as a result we obtain \(Q_i+d\cdot 2^{-(i+1)}\). Substituting the value of \(Q_i\), we shall have
\[ Q_i+d\cdot 2^{-(i+1)}=Q_{i+1}-d\cdot 2^{-i}+d\cdot 2^{-(i+1)} . \tag{10} \]
After transforming the right-hand side of (10),
\[ Q_i+d\cdot 2^{-(i+1)}=Q_{i-1}-d\cdot 2^{-(i+1)} . \tag{11} \]
It is evident that the obtained remainder (the right-hand side of the equality) is the difference between the last positive remainder \(Q_{i-1}\) and the divisor shifted in advance for the \((i+1)\)-st cycle. Consequently, the last positive remainder is restored automatically, with a relative shift and subtraction from it of this shifted divisor, i.e., precisely what is provided for by the first method.
From our point of view, a more logical approach is a direct proof based on transforming the expression for the negative remainder \(Q_i\) obtained in accordance with the procedure of the first method. Suppose that \(Q_i<0\). According to the procedure adopted in the first method, \(Q_{i-1}\) is restored \(\bigl(Q_{i-1}=Q_i+d\cdot 2^{-i}\bigr)\), the divisor is shifted (the value \(d\cdot 2^{-(i+1)}\) is obtained), and it is subtracted from \(Q_{i-1}\) \(\bigl(Q_{i-1}-d\cdot 2^{-(i+1)}\bigr)\); as a result, \(Q_{i+1}\) is obtained.
Substituting the corresponding expression for \(Q_{i-1}\), we obtain
\[ Q_{i+1}=Q_i+d\cdot 2^{-i}-d\cdot 2^{-(i+1)} . \tag{12} \]
After transforming the right-hand side of this expression, we obtain
\[ Q_{i+1}=Q_i+d\cdot 2^{-(i+1)} . \tag{13} \]
It is evident that the remainder \(Q_{i+1}\), needed for forming the corresponding digit of the quotient, can be obtained from the preceding negative remainder by adding to it the divisor shifted in advance.
Since in any division method the last positive remainder is ultimately restored, and in the first method an appropriate operation is provided for this purpose, while in the second, as noted in [1], restoration takes place automatically, in our opinion it is more appropriate to call the first method the division method with explicit restoration of the remainder, and the second the division method without explicit restoration of the remainder.
References
-
B. V. Anisimov, V. N. Chetverikov. Fundamentals of the Theory and Design of Digital Computers. Moscow, “Vysshaya shkola,” 1970.
-
Yu. V. Gavrilov, A. N. Puchko. Arithmetic Units of High-Speed Digital Computers. Moscow, “Sovetskoe radio,” 1970.
-
M. A. Kartsev. Arithmetic of Digital Machines. Moscow, Fizmatgiz, 1970.