US 5,068,816 A · Interplating memory function evaluation

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.

Claims5

Dependent claims

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.sup.2, t.sup.3, . . . , t.sup.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.

Dependencies are inferred from the claim text.

Interplating memory function evaluation

Life of this patent

Interplating memory function evaluation

Life of this patent

Abstract

Claims5