Early detection of overflow and exceptional quotient/remainder pairs for nonrestoring twos complement division

An arithmetic processing system that performs nonrestoring division of a 2n bit dividend N by an n bit divisor D to obtain, for non-overflow division operations, an n bit quotient Q and an n bit remainder R (or signal overflow or divide by zero), with N, D, Q, and R being in 2's complement format, the division system performing early overflow detection of all overflow conditions based on an input dividend N and an input divisor D, and a first partial remainder of value N-2.sup.n-1 D, comprising:

• (a) iterative divide means for receiving the input dividend N and the input divisor D, where (i) the input dividend N is characterized by a 2-bit sign field N(s1s2) formed by a first sign bit N(s1) and a second sign bit N(s2), a high order n-1 dividend magnitude bits N(himag), and a low order n-1 dividend magnitude bits N(lomag), such that N(s1) and N(himag) form a 2's complement number N(hi), and where (ii) the input divisor D is characterized by a leading sign bit D(s) and n-1 divisor magnitude bits D(mag);
• (b) in a first iterative operation, the iterative divide means computing the difference between N(hi) and D to obtain an n-bit first partial remainder PR1 corresponding to the first n bits of the first partial remainder of value N-2.sup.n-1 D including a leading sign bit PR1(s);
• and
• (c) early overflow detection means including (i) exceptional divisor means for performing an exceptional divisor test, (ii) exceptional dividend means for performing an exceptional dividend test, and (iii) exceptional quotient means for performing an exceptional quotient test;
• (d) for the exceptional divisor test, the exceptional divisor means determining whether D(mag) is equal to zero and D(s) is equal to one, thereby indicating that D=-2.sup.n-1, and if so, signaling overflow if (i) N(s1s2) are ›01!, and N(himag) is not zero, or (ii) N(s1s2) are ›10!, or (iii) N(s1s2) are ›11!, and both N(himag) and N(lomag) are zero;
• (e) for the exceptional dividend overflow test, if the exceptional divisor means determines that D(mag) is not equal to zero, then the exceptional dividend means signaling overflow if N(s1) is not equal to N(s2), thereby indicating that the dividend is too large for any divisor;
• and
• (f) for the exceptional quotient test, if the exceptional divisor means determines that D(mag) is not equal to zero, and the exceptional dividend means does not signal overflow, then the exceptional quotient means invoking either (i) a first EQ test if PR1(s) is equal to N(s1), or (ii) a second EQ test if PR1(s) is not equal to N(s1);
• (g) for the first EQ test, overflow is signaled (i) if N(s1) is equal to D(s) denoting that Q.gtoreq.2.sup.n-1, or (ii) if N(s1) is not equal to D(s) denoting that Q.ltoreq.-2.sup.n-1, then if the values of PR1 and N(lomag) do not form an appropriately bounded remainder for a quotient Q equal to ›-2.sup.n-1 !, thereby indicating that Q.ltoreq.-2.sup.n-1 -1;
• or
• (h) for the second EQ test, signaling overflow if N(s1)=›1!, D(s)=›1!, N(lomag)=0, and PR1=0, thereby denoting that Q=2.sup.n-1 and R=0.

A method for performing nonrestoring division using an adder that performs addition, subtraction, and complementation operations, iteratively dividing a 2n bit dividend N by an n-bit divisor D to compute an n bit quotient Q and an n bit remainder R (or signal overflow or divide by zero), where N, D, Q, and R are in 2's complement format, and where the dividend N includes high and low magnitude fields N(himag) and N(lomag), the method including performing early overflow detection of all overflow conditions based on an input dividend N and an input divisor D, and a first partial remainder of value N-2.sup.n-1 D, comprising the steps:

• (a) computing, using the adder, the first partial remainder from the input divisor D and the input dividend N;
• (b) generating a D(mag)-zero indication of whether a divisor magnitude field of D is zero,
• (c) generating N(himag)-zero and N(lomag)-zero indications of whether N(himag) and N(lomag) respectively are zero;
• (d) generating a PR-zero indication of whether the first partial remainder is zero;
• (e) generating a ›-2.sup.n-1 !-quotient indication of whether the value of the sum of the first partial remainder of value N-2.sup.n-1 D and the input divisor D is positive, negative, or zero;
• (f) for every overflow condition, generating an overflow signal from (i) selected sign bits of the input dividend N, (ii) a sign bit of the divisor D, (iii) a sign bit of the first partial remainder, (iv) the D(mag)-zero indication, (v) the PR-zero indication, (vi) the N(himag)-zero and N(lomag)-zero indications;
• and (vii) the ›-2.sup.n-1 !-quotient indication.

An arithmetic processing system that performs nonrestoring division of a 2n bit dividend N by an n bit divisor D to obtain, for non-overflow division operations, an n bit quotient Q and an n bit remainder R (or signal overflow or divide by zero), with N, D, Q, and R being in 2's complement format, the arithmetic processing system performing early detection of overflow conditions and selected exceptional quotient/remainder pairs based on an input dividend N and an input divisor D, and a first partial remainder PR1 of value N-2.sup.n-1 D, comprising:

• (a) iterative divide means, responsive to the input dividend N and the input divisor D, for computing said first partial remainder PR1;
• (b) overflow means, responsive to the divisor D, the dividend N, and the computed first partial remainder PR1, for signaling all cases of overflow;
• and
• (c) exceptional Q/R means, responsive to the divisor D, the dividend N, and the computed first partial remainder PR1, for outputting said selected exceptional quotient/remainder pairs in which either the value of the divisor D is -2.sup.n-1 or the value of the quotient Q is -2.sup.n-1 ;
• (d) if said overflow means does not signal overflow, and if said exceptional Q/R means does not output exceptional quotient/remainder pairs, said iterative divide means computing said quotient Q and said remainder R by performing successive iterative operations.