Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2003-04-18
2004-08-17
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06779012
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 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 speed (CPA and CSAs) is a long standing issue faced by computer divider and square root designers.
SUMMARY OF THE INVENTION
In a computer system, a next partial remainder and an output digit is determined by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the root digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.
The signed digit values are selected from a set of digit values. The adder computes a carry out bit independent of the carry in bit. The scaler computes the next signed digit partial remainder by scaling the current signed digit partial remainder upward.
In a computer system, a mathematical square root operation is performed by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the root digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.
The signed digit values are selected from a set of digit values. The set of digit values may be minus one, zero or one, or minus two, minus one, zero, plus one and plus two or any other set of digit values containing more than two digit values. The adder computes a carry out bit independent of the carry in bit. The output signals in the adder may be initialized to predetermined voltage levels. The scaler computes the next signed digit partial remainder by scaling the current signed digit remainder upward.
In a computer system, a mathematical division operation is performed by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the quotient digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.
REFERENCES:
patent: 4725974 (1988-02-01), Kanazawa
patent: 4797849 (1989-01-01), Nakano
patent: 4939686 (1990-07-01), Fandriarto
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: 5954789 (1999-09-01), Yu et al.
patent: 6108682 (2000-08-01), Matheny
patent: 2003/0028574 (2003-02-01), Takagi
Burgess, N., “A Fast Division Algorithm for VLSI”, Department of Electrical Engineering and Electronics, Uxbridge, U.K.: Brunel University (1991).
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, CA, 807-811 (1993).
Ciminiera, L. and Montuschi, P., “On the Efficient Implementation of Higher Radix Square Root Algorithms,” Dipartimento di Automatica e Informatica, corso Duca degli Abruzzi 24, 10129 Torino (Italy), Proceedings of 9th Symposium on Computer Arithmetic, 154-161 (1989).
Koren, Israel, “Computer Arithmetic Algorithm,” Prentice Hall, N.J., ch. 7-8, pp. 127-161.
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.
Ciminiera, L. and P. Montuschi, “Higher Radix Square Rooting,” IEEE Transactions on Computers, vol. 39, No. 10, Oct. 1990, pp. 1220-1231.
Dupcak Robert J.
Krause Jonathan D.
Matson Mark D.
Samudrala Sridhar
LandOfFree
Computer method and apparatus for division and square root... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer method and apparatus for division and square root..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer method and apparatus for division and square root... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323387