US5068816A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interplating memory function evaluation
Assignee: Individual
•
Filing: 1990-02-16
•
Granted: 1991-11-26
•
Expires: 2010-02-16
Abstract
Abstract A technique for the evaluation of a general continuous function f(x) is presented, and the design of an interpolating memroy, an implementation of the technique, is described. The technique partitions the domain of f(x) into segments, and defines an interpolating (or approximating) function for each. The implementation is a memory subsystem that holds the parameters of the approximating functions and yields an interpolated function value on each read reference. Polynomial interpolating functions are considered in particular. Hardware requirements (memory and computational logic) are analyzed in terms of the required precision. It is shown that as long as f(x) has d+1 derivatives, and d is the degree of the interpolating polynomial, d+1 additional bits of precision of the computer f(x) are obtained for each additional address bit used in the interpolating memory. This establishes a tradeoff between memory and computational logic, which can be exploited in the design of a unit for a specific function, for any precision requirement. Furthermore, a single unit may be designed for any class of functions that have the required derivatives. Two examples of implementations for particular functions are presented.
Inventors
- 👤 Andrew S. Noetzel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 06:42
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/17; G06F1/00; G06F1/02; G06F1/03; G06F1/035; G06F1/0356; G06F2101/00; G06F2101/04; G06F2101/10
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
230 words
An interpolating memory function evaluation apparatus, comprising: a memory address means for accessing a memory unit by using first bits of a function argument for the memory unit address, an approximating means for obtaining parameters of an approximating function from the memory unit, and an evaluating means for evaluating the approximating function, using other bits of the function argument, the specific approximating function whose parameters were obtained from the memory unit, wherein the accessing comprises using k bits of the function argument to address the memory unit wherein the memory unit contains polynomial coefficients, wherein the evaluating comprises evaluating with fixed combinational logic a degree d-polynomial whose coefficients are obtained from the memory unit, using as the polynomial argument the bits of the function argument of lower order than the k bits used to address the memory unit, wherein the evaluation of the polynomial is performed using as an input to a polynomial evaluator a value t comprised of bits of the function argument of lower order than the k bits used to address the memory unit, computing the quantities t 2 , t 3 , . . . , t d in fixed combinational logic, computing terms of the polynomial in a set of multipliers operating in parallel, whose inputs are the coefficients obtained from the memory unit and the powers of t, and adding terms of the polynomial.
Claim 2
Dependent Claim
230 words
An interpolating memory function evaluation apparatus, comprising: a memory address means for accessing a memory unit by using first bits of a function argument for the memory unit address, an approximating means for obtaining parameters of an approximating function from the memory unit, and an evaluating means for evaluating the approximating function, using other bits of the function argument, the specific approximating function whose parameters were obtained from the memory unit, wherein the accessing comprises using k bits of the function argument to address the memory unit wherein the memory unit contains polynomial coefficients, wherein the evaluating comprises evaluating with fixed combinational logic a degree d-polynomial whose coefficients are obtained from the memory unit, using as the polynomial argument the bits of the function argument of lower order than the k bits used to address the memory unit, wherein the evaluation of the polynomial is performed using as an input to a polynomial evaluator a value t comprised of bits of the function argument of lower order than the k bits used to address the memory unit, computing the quantities t 2 , t 3 , . . . , t d in fixed combinational logic, computing terms of the polynomial in a set of multipliers operating in parallel, whose inputs are the coefficients obtained from the memory unit and the powers of t, and adding terms of the polynomial.
Claim 3
Dependent Claim
146 words
The apparatus of claim 1, further comprising accepting a floating-point function argument, with exponent field E and mantissa M, and using k function argument bits, including zero or more low order bits of E and zero or more high order bits of M as an address of a register set in a set-associative memory, performing an associative search in the associative memory set selected by the address, using the high order bits of E as the associative search key, obtaining from the memory location associated with a successful match in the associative memory, a floating-point exponent of a function value and the d+1 polynomial coefficients, evaluating the polynomial specified by the coefficients with polynomial argument specified as the low-order bits of M, and normalizing the floating-point value consisting of the exponent obtained from the memory and the mantissa obtained as a result of the polynomial evaluation.
Claim 4
Dependent Claim
36 words
The apparatus of claim 2, wherein a particular function to be evaluated is supplied as a function identification f, and the associative search key is comprised of both f and the high order bits of E.
Claim 5
Independent Claim
192 words
An apparatus for evaluating floating-point functions, comprising a first input for inputting a function identification f, a second input for inputting an argument x in floating-point form with exponent E and mantissa M, means for supplying the function identification f input to a set-associative memory, means for supplying high order bits of E to the set-associative memory, means for supplying low order bits of E and high order bits of M to a set selection input of the associative memory, for selecting a portion of the associative memory, means for making an associative search in the selected portion of the memory with f and the high order bits of E, means for selecting, as a result of the associative search, a memory word containing polynomial coefficients and a floating-point exponent, means for supplying parallel outputs of a polynomial coefficients to a polynomial evaluation unit, means for supplying low order bits of M to the polynomial evaluation unit, means for supplying the floating-point exponent and an output of the polynomial evaluation unit to a floating-point normalization unit in obtaining floating-point representation of the function evaluation from the normalization unit M of the normalizer.
Claim 6
Independent Claim
192 words
An apparatus for evaluating floating-point functions, comprising a first input for inputting a function identification f, a second input for inputting an argument x in floating-point form with exponent E and mantissa M, means for supplying the function identification f input to a set-associative memory, means for supplying high order bits of E to the set-associative memory, means for supplying low order bits of E and high order bits of M to a set selection input of the associative memory, for selecting a portion of the associative memory, means for making an associative search in the selected portion of the memory with f and the high order bits of E, means for selecting, as a result of the associative search, a memory word containing polynomial coefficients and a floating-point exponent, means for supplying parallel outputs of a polynomial coefficients to a polynomial evaluation unit, means for supplying low order bits of M to the polynomial evaluation unit, means for supplying the floating-point exponent and an output of the polynomial evaluation unit to a floating-point normalization unit in obtaining floating-point representation of the function evaluation from the normalization unit M of the normalizer.
Claim 7
Dependent Claim
201 words
A floating-point interpolating memory, comprising a floating-point argument input having an exponent section and an mantissa section, a function identification input, a set-associative memory having a function input and an exponent input, the function input being connected to the function identification input, high order bits in the exponent section being connected to the exponent input of the set-associative memory, a set-selector connected to the set-associative memory, at least one of low order bits from an exponent register and high order bits from a mantissa register being connected to the set selector for selecting associative memory set from the set-associative memory, a word memory unit connected to the set-associative memory having words selected by an associative search in the selected set, the selected memory words including a floating-point exponent and polynomial coefficients, a polynomial evaluator connected to plural outputs of the word memory unit holding the polynomial coefficients, the polynomial evaluator having an input connected to low order bits from the input mantissa register, a floating-point normalization unit connected to an output of the polynomial evaluator and having an input connected to a floating-point exponent obtained from the word memory unit, the floating-point normalization unit having an output of the function evaluation.
Claim 8
Dependent Claim
201 words
A floating-point interpolating memory, comprising a floating-point argument input having an exponent section and an mantissa section, a function identification input, a set-associative memory having a function input and an exponent input, the function input being connected to the function identification input, high order bits in the exponent section being connected to the exponent input of the set-associative memory, a set-selector connected to the set-associative memory, at least one of low order bits from an exponent register and high order bits from a mantissa register being connected to the set selector for selecting associative memory set from the set-associative memory, a word memory unit connected to the set-associative memory having words selected by an associative search in the selected set, the selected memory words including a floating-point exponent and polynomial coefficients, a polynomial evaluator connected to plural outputs of the word memory unit holding the polynomial coefficients, the polynomial evaluator having an input connected to low order bits from the input mantissa register, a floating-point normalization unit connected to an output of the polynomial evaluator and having an input connected to a floating-point exponent obtained from the word memory unit, the floating-point normalization unit having an output of the function evaluation.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-11-25 | 1995-05-27 | 1995-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-11-25 | 1999-05-27 | 1999-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-11-25 | 2003-05-27 | 2003-11-26 | $7700.00 | Window Closed / Lapsed |