Data processing: generic control systems or specific application – Specific application – apparatus or process – Article handling
Reexamination Certificate
1995-08-22
2001-05-29
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Article handling
C700S222000, C700S222000, C700S222000, C700S222000, C712S221000, C712S223000
Reexamination Certificate
active
06240338
ABSTRACT:
FIELD OF THE INVENTION
This pertains to the field of computers. In particular, this pertains to methods and apparatus for computing reciprocals and performing divide operations.
BACKGROUND OF THE INVENTION
Computers are well known for their ability to perform mathematical functions at a high rate of speed. In order to achieve such speed, computers use various techniques to perform mathematical functions on given operands. Limitations in the representation of numbers and in numerical calculations within the computer lead to computed results that are only accurate to within some known or estimated error term. The ability to perform basic functions such as addition, subtraction, multiplication, and division to a consistent accuracy in a timely manner is a consideration in computational performance of the computer system.
One technique for implementing a mathematical function is to implement the function in hardware. Math functions including addition and subtraction might be accomplished by performing the steps of 1) loading registers with the operands; 2) executing the operational code (“opcode”) for the desired function; and then, 3) retrieving the result from one or more registers. The opcode is simply a command to perform the function implemented in hardware.
One disadvantage of this prior art technique is that some functions, such as division, typically require several cycles for completion which in turn tends to adversely affect system performance.
An alternative method of computing other results, such as reciprocals
(
i
.
e
.
,
f
(
x
)
=
1
x
)
,
often involves looking the result up in a table. For example, the steps for computing a reciprocal might include 1) scaling or normalizing an operand; 2) looking up a reciprocal value corresponding to the normalized value in a lookup “seed” table; and 3) scaling or denormalizing the looked up value to reflect the reciprocal of the denormalized operand. The lookup table is typically stored in a read only memory (ROM). The error associated with this technique is controlled to a great extent by the “height” and “width” or the precision of the entry in the lookup table.
One disadvantage of the conventional lookup approach is that the area required to store the lookup table on the integrated circuit may prevent the lookup approach from being a cost effective technique for given precision requirements.
A cost effective way of implementing mathematical functions such as reciprocal or division to within a consistent error margin in a given time frame is a desirable feature of a computer system.
SUMMARY AND OBJECTS OF THE INVENTION
Methods and apparatus for computing reciprocals and performing divide operations in a computer are described.
A reciprocal of an operand is determined by looking up an estimated reciprocal term in a first lookup table stored in a first computer memory wherein the estimated reciprocal term corresponds to at least a portion of the operand. An error term is looked up in a second lookup table stored in a second computer memory. The error term corresponds to at least a portion of the operand. The reciprocal is generated from the estimated reciprocal term and the error term.
A method of performing a divide operation in a computer includes the step of looking up an estimated reciprocal term in a first lookup table stored in a first computer memory. The estimated reciprocal term corresponds to at least a portion of a given divisor. A reciprocal error term is looked up in a second lookup table stored in a second computer memory. The reciprocal error term corresponds to at least a portion of the divisor. A reciprocal of the divisor is generated from the estimated reciprocal term and the error term. A dividend is multiplied by the reciprocal of the divisor to generate a quotient.
An apparatus for computing a reciprocal of an operand includes a first memory containing estimated reciprocal terms, and a second memory containing reciprocal error terms. The apparatus further includes an adder for adding a selected estimated reciprocal term from the first memory and a selected reciprocal error term from the second memory to provide the reciprocal, wherein the selected estimated reciprocal term and the selected reciprocal error term correspond to at least a portion of the operand.
An apparatus for performing a divide operation includes a first memory containing estimated reciprocal terms, and a second memory containing reciprocal error terms. The apparatus also includes an adder for adding a selected estimated reciprocal term from the first memory and a selected reciprocal error term from the second memory to provide the reciprocal. The selected estimated reciprocal term and the selected reciprocal error term correspond to at least a portion of a divisor. A multiplier multiplies a dividend by the reciprocal to generate a quotient.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 4413326 (1983-11-01), Wilson et al.
patent: 5012438 (1991-04-01), Yamaguchi
patent: 5068816 (1991-11-01), Noetzel
patent: 5079716 (1992-01-01), Lenhardt et al.
patent: 5157624 (1992-10-01), Hesson
patent: 5220524 (1993-06-01), Hesson
patent: 5249149 (1993-09-01), Cocanougher et al.
patent: 5305248 (1994-04-01), Ammann
patent: 5341321 (1994-08-01), Krap et al.
patent: 5499272 (1996-03-01), Bottomley
Dorsey & Whitney LLP
Grant William
Micro)n Technology, Inc.
Patel Ramesh
LandOfFree
Seed ROM for reciprocal computation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Seed ROM for reciprocal computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Seed ROM for reciprocal computation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2564303