Quotient digit selection logic for floating point...

Details Quotient digit selection logic for floating point... Quotient digit selection logic for floating point...

1999-09-03

2003-07-15

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S653000

Reexamination Certificate

active

06594681

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of floating point dividers in microprocessors. Specifically, the present invention relates to quotient digit selection rules in SRT division/square root implementations which prevent negative final partial remainders from occurring when results are exact, and which provide support for correct rounding in all rounding modes.
2. The Background Art
The SRT algorithm provides one way of performing non-restoring division. See, J. E. Robertson, “A new class of digital division methods,”
IEEE Trans. Comput
., vol. C-7, pp. 218-222, Sep. 1958, and K. D. Tocher, “Techniques of multiplication and division for automatic binary computers,”
Quart. J. Mech. Appl. Math., vol
. 11, pt. 3, pp. 364-384, 1958. Digital division takes a divisor and a dividend as operands and generates a quotient as output. The quotient digits are calculated iteratively, producing the most significant quotient digits first. In SRT division, unlike other division algorithms, each successive quotient digit is formulated based only on a few of the most significant partial remainder digits, rather than by looking at the entire partial remainder, which may have a very large number of digits. Since it is not possible to insure correct quotient digit selection without considering the entire partial remainder in any given iteration, the SRT algorithm occasionally produces incorrect quotient digit results. However, the SRT algorithm provides positive, zero, and negative quotient digit possibilities. If the quotient digit in one iteration is overestimated, then that error is corrected the next iteration by selecting a negative quotient digit. In SRT division, quotient digits must never be underestimated; quotient digits must always be overestimated or correctly estimated. By never underestimating any quotient digits, the partial remainder is kept within prescribed bounds so as to allow the correct final quotient to be computed. Because the SRT algorithm allows negative quotient digits, the computation of the final quotient output usually involves weighted adding and subtracting of the quotient digits, rather than merely concatenating all the quotient digits as in normal division.
The higher the radix, the more digits of quotient developed per iteration but at a cost of greater complexity. A radix-2 implementation produces one digit per iteration; whereas a radix-4 implementation produces two digits per iteration. FIG.
1
illustrates a simple SRT radix-2 floating point implementation. The simple SRT radix-2 floating point implementation shown in
FIG. 1
requires that the divisor and dividend both be positive and normalized; therefore, ½≦D, Dividend≦1. The initial shifted partial remainder, 2PR[
0
], is the dividend. Before beginning the first quotient digit calculation iteration, the dividend is loaded into the partial remainder register 100; thus, the initial partial remainder is the dividend. Subsequently, the partial remainders produced by iteration are developed according to the relationship
PR
i+1
=2
PR
i
−q
i+1
D
  (R.1)
In relationship (R.1), q
i+1
is the quotient digit, and has possible values of −1, 0, or +1. This quotient digit q
i+1
is solely determined by the value of the previous partial remainder and is independent of the divisor. The quotient selection logic
102
takes only the most significant four bits of the partial remainder as input, and produces the quotient digit. In division calculations, the divisor remains constant throughout all iterations. However, square root calculations typically involve adjustments to the divisor stored in the divisor register
101
after each iteration. Therefore, the independence of the quotient digit selection on the divisor is an attractive feature for square root calculations.
The partial remainder is typically kept in redundant carry save form so that calculations of the next partial remainder can be performed by a carry-save adder instead of slower and larger carry-propagate adders. The partial remainder is converted into non-redundant form after all iterations have been performed and the desired precision has been reached. Because the SRT algorithm allows overestimation of quotient digits resulting in a negative subsequent partial remainder, it is possible that the last quotient digit is overestimated, so that the final partial remainder is negative. In that case, since it is impossible to correct for the overestimation, it is necessary to maintain Q and Q−1, so that if the final partial remainder is negative, Q−1 is selected instead of Q. The quotient digits are normally also kept in redundant form and converted to non-redundant form at the end of all iterations. Alternatively, the quotient and quotient minus one (Q and Q−1) can be generated on the fly according to rules developed in M. D. Ercegovac and T. Lang, “On-the-fly rounding,” IEEE Trans. Comput., vol. 41, no. 12, pp. 1497-1503, December 1992.
The SRT algorithm has been extended to square root calculations allowing the utilization of existing division hardware. The simplified square root equation looks surprisingly similar to that of division. See, M. D. Ercegovac and T. Lang, “Radix-4 square root without initial PLA”, IEEE Trans. Comput., vol. 39, no. 8, pp. 1016-1024, August 1990. The iteration equation for square root calculations is as-follows.
PR
i+1
=2
PR
i
−q
i−1
(2
Q
i
+q
I+1
2
−(I+1)
  (R.2)
In relationship (R.2), the terms in parentheses are the effective divisor. For square root calculations, the so-called divisor is a function of Q
i
, which is a function of all the previous root digits q
1
through q
i
. The root digits hereinafter will be referred to as “quotient digits” to maintain consistency in terminology. Therefore, in order to support square root calculation using the same hardware as used for division, on-the-fly quotient generation is required in order to update the divisor after each iteration.
Binary division algorithms are analogous to standard base 10 long division. In R/D=Q, each quotient digit for Q is guessed. In order to determine the first quotient digit, a guess for the proper quotient digit is multiplied by the divisor, and that product is subtracted from the dividend to produce a remainder. If the remainder is greater than the divisor, the guess for the quotient digit was too small; if the remainder is negative, the guess for the quotient digit was too large. In either case, when the guess for the quotient digit is incorrect, the guess must be changed so that the correct quotient digit is derived before proceeding to the next digit. The quotient digit is correct when the following relation is true: 0≦PR≦D, in which PR stands for the partial remainder after subtraction of the quotient digit multiplied by the divisor.
The key to the SRT division algorithm is that negative quotient digits are permitted. For example, in base 10, in addition to the standard digits 0 through 9, quotient digits may take on values of −1 through −9. Consider the division operation 600/40. If the correct quotient digits are selected for each iteration, the correct result is 15. However, assume for the moment that during the first iteration, a quotient digit of 2 was incorrectly guessed instead of the correct digit of 1. The partial remainder after 2 has been selected as the first quotient digit is 600−(2*40*10
1
)=−200. According to SRT division, this error can be corrected in subsequent iterations, rather than having to back up and perform the first iteration again. According to SRT division, assume that the second quotient digit is correctly guessed to be −5. The partial remainder after that iteration will be −200−(−5*40*10
0
)=0. When the partial remainder after an iteration is zero, the correct values for all the remaining digits are zeros. Thus, the computed result is 2*10&pri

Affiliated with

Also associated with

Rating

Quotient digit selection logic for floating point... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Quotient digit selection logic for floating point..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quotient digit selection logic for floating point... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3020089