Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-31
2004-05-04
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S629000
Reexamination Certificate
active
06732135
ABSTRACT:
BACKGROUND OF THE INVENTION
Generally mathematical operations in a computer such as, (i) division of a dividend by a divisor to produce a quotient and (ii) square root of a radicand to produce a root, are slow. Such division and square root operations are slow because they require iteratively generating a series of partial remainders, and quotient or root digits respectively.
Therefore, the speed of the division or square root operation is dependent on the amount of time it takes to complete one iteration and the total number of iterations required. The total number of iterations is dependent on the number of quotient or root mantissa digits required to provide an accurate quotient or root. For example, in floating point division twenty-four mantissa digits are required for single precision and fifty-three mantissa digits are required for double-precision, therefore the time required to generate each of the required quotient digits is critical to the overall speed of the division operation.
Typically, in each iteration of a square root operation, a root digit and a correction term are computed after examining a current partial remainder. The succeeding or partial remainder for the next iteration is computed by subtracting the correction term from the current partial remainder and scaling the result of the subtraction. In each iteration of a division operation, a quotient digit is computed after comparing a current partial remainder and the divisor. The partial remainder for the next iteration is computed by subtracting a multiple of the divisor from the current partial remainder and scaling the result of the subtraction.
Thus, the computation of the partial remainder for the next iteration for both the square root operation and the division operation requires a subtraction operation. Typically the subtraction is performed through the use of Carry Propagate Adders (“CPA”) or Carry Save Adders (“CSA”). CPAs are relatively slow because a carry bit must be propagated from the Least Significant Bit (“LSB”) CPA to the Most Significant Bit (“MSB”) CPA. CSAs are much faster but because they present the partial remainder as separate sum and carry binary numbers which must be added, examination of the partial remainder is slower and more complicated.
The tradeoff between examination speed and subtraction efficient speed (CPA and CSAs) is a long standing issue faced by computer divider and square root designers. Another long standing issue is the accumulation of root digit and quotient digits. The rate of accumulation of partial roots and/or quotients needs to be fast enough to support the rate of the main square root/division loop. This in turn determines how fast the overall square root/division operation is performed.
SUMMARY OF THE INVENTION
The present invention describes a method and apparatus for accumulating quotient and/or square root digits in an efficient manner. In particular, the present invention accumulates the quotient in carry-save form along with proper sign extension, using only one carry-save adder. By using minimal logic in the accumulation loop, the present invention provides a method and apparatus for accumulating partial quotients at a rate fast enough to support the rate of fast dividers.
In the preferred embodiment, a digital processor preforms a division operation on a dividend in a main loop. From this, quotient digits (i.e., partial quotients) are produced. A quotient accumulates receives and properly reconciles the quotient digits across all iterations in an efficient manner as follows.
The quotient accumulator is formed of a set of multiplexes coupled to a single carry-save adder. The multiplexes receive as input, prior accumulated quotient digits, partial quotient digits output from the main loop and sign extension digits corresponding to the partial quotient digits. The number of outputs of the multiplexes is less than the number of inputs.
The single carry-save adder receives as inputs the outputs from the multiplexes which number within the range acceptable by the carry-save adder. The carry-save adder produces than appropriate accumulated quotient and preferably at a rate fast enough to support the rate of the main loop.
Preferably the partial quotient digits output from the main loop and input to the multiplexes is in carry-save format. The partial quotient digits may include sum bits and carry bits from one iteration of the main loop and carry bits delayed from a prior iteration.
In accordance with one feature of the present invention, the sign extension digits are bit (possible fragmented bit strips) from a single constant value representing sign extensions of all partial quotients. Further included in the sign extension digits are switch bits for changing a strip of logic ones to logic zeros.
REFERENCES:
patent: 4725974 (1988-02-01), Kanazawa
patent: 4797849 (1989-01-01), Nakano
patent: 4939686 (1990-07-01), Fandrianto
patent: 5046038 (1991-09-01), Briggs et al.
patent: 5065352 (1991-11-01), Nakano
patent: 5105378 (1992-04-01), Mori
patent: 5128891 (1992-07-01), Lynch et al.
patent: 5365471 (1994-11-01), Sato
patent: 5404324 (1995-04-01), Colon-Bonet
patent: 5467299 (1995-11-01), Sato et al.
patent: 5537345 (1996-07-01), Nakano
patent: 5787030 (1998-07-01), Prabhu et al.
patent: 5798955 (1998-08-01), Matsubara
patent: 6108682 (2000-08-01), Matheny
Koren, I., “Fast Division.” InComputer Arithmetic Algorithms,(Englewood Cliffs, NJ: Prentice Hall), pp. 127-151.
Koren, I., “Division Through Multiplication.” InComputer Arithmetic Algorithms,(Englewood Cliffs, NJ: Prentice Hall,) pp. 153-161.
Ren, H., et al, “Design of a 16-Bit CMOS Divider/Square-Root Circuit,”Department of Electrical Engineering, College of Engineering, San Jose State University, San Jose, California:807-811 (1993).
Ciminiera, L. and Montuschi, P., “Higher Radix Square Rooting,”IEEE Transactions on Computers,39 (10): 1220-1231 (Oct. 1990).
Montuschi, P. and Ciminiera, L., “On the Efficient Implementation of Higher Radix Square Root Algorithms,”Dipartimento di Automatica e Informatica, Politecnico di Torino, corso Duca degli Abruzzi 24, 10129 Torino(Italy), 154-161.
Burgess, N., “A Fast Division Algorithm for VLSI,”IEEE International Conference on Computer Design: VLSI in Computers and Processors:560-563 (1991).
Wong, D. and M. Flynn, “Fast Division Using Accurate Quotient Approximations to Reduce the Number of Iterations,”IEEE Transactions on Computers, vol. 41, No. 8, Aug. 1992 (pp. 981-995).
Clouser John D.
Grundmann William R.
Samudrala Sridhar
Hewlett--Packard Development Company, L.P.
Malzahn David H.
LandOfFree
Method and apparatus for accumulating partial quotients in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for accumulating partial quotients in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for accumulating partial quotients in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3198472