Approximation circuit and method

Details Approximation circuit and method Approximation circuit and method

1999-05-12

2003-06-17

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06581085

ABSTRACT:

BACKGROUND OF THE INVENTION
Functional approximation circuits, such as reciprocal approximation circuits, are known in the art. For example, a division (e.g., in 2D and 3D graphics implementations) is typically implemented using a reciprocal approximation circuit. The resulting reciprocal approximation of the divisor is multiplied with the dividend, thereby emulating the divide operation.
A conventional reciprocal approximation circuit uses an iterative method (e.g., the Newton-Raphson method) based on an initial estimate. Reciprocal approximations are fed back through the circuit until a reciprocal approximation of a desired precision is obtained. This iterative process takes significant time. Thus, a faster circuit and method for approximating, for example, a reciprocal are desired.
SUMMARY OF THE INVENTION
An approximation circuit approximates a function f(x), given an input value “x”, by computing and adding at least the first two terms in a Taylor series (i.e., f(a) and f′(a)(x−a)) where “a” is an approximation value reasonably close to the input value “x”. For example, “a” may share the most significant bits of input value “x”. The values f(a) and f′(a) can be provided by look-up tables. A first look-up table receives the approximation value “a”, and provides a function f(a). Similarly, a second look-up table receives the approximation value “a” and provides a first derivative f′(a) of the function f(a). A multiplier then multiplies the value f′(a) represented by the bits generated by the second look-up table by a difference (x−a) between value “x” and value “a”. An adder adds the first term represented by the bits generated by the first look-up table and the second term represented by the bits generated by the multiplier to provide an approximation of f(x).
In one embodiment, the third term (i.e., (½)f″(a)(x−a)
2
) of the Taylor series is also computed. For example, a third look-up table receives the approximation value “a” and provides a value of one half of the second derivative (½)f″(a) of the function f(a). A fast squaring circuit receives the difference (x−a) and generates bits representing the square (x−a)
2
. Another multiplier receives the value (½)f″(a) and the value (x−a)
2
to generate the third term (½)f″(a)(x−a)
2
.
Since the terms of the Taylor series are computed in parallel, an adder adds all the terms simultaneously to obtain the approximation. Since no iteration is performed, the approximation circuit of the present invention is faster than conventional approximation circuits.


REFERENCES:
patent: 4482975 (1984-11-01), King et al.
patent: 5179659 (1993-01-01), Lien et al.
patent: 5274580 (1993-12-01), Keryvel et al.
patent: 5963460 (1999-10-01), Rarick

Affiliated with

Also associated with

Rating

Approximation circuit and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Approximation circuit and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation circuit and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3136339