METHOD AND APPARATUS FOR FUNCTION APPROXIMATION USING MULTI-LEVEL LOOKUP TABLE
A method and an apparatus are disclosed for a function approximation using a multi-level lookup table. The function approximation device and the method approximate function values for a function in multiple stages using a multi-level lookup table (LUT) in approximating nonlinear function values based on piecewise linear approximation or piecewise polynomial approximation. In the multi-level LUT, a segment length is set differently depending on the amount of change in the function in order to reduce approximation errors.
1 . A piecewise function approximation method performed by a computing device, comprising:
obtaining an input variable value for a function;
extracting approximation coefficients for the function using a multi-level lookup table (LUT) based on the input variable value, the multi-level LUT including K (K being a natural number of 2 or more) LUTs; and
calculating a function value for the input variable value using the approximation coefficients,
wherein the K LUTs support different segment sizes, a segment size supported by a k-th (k being a natural number from 1 to K−1) LUT is greater than a segment side supported by a (k+1)-th LUT, and the (k+1)-th LUT is accessed based on mapping information provided by the k-th LUT.
2 . The piecewise function approximation method of claim 1 , wherein the mapping information is information for dividing each of t segments (t being a natural number) into sub-segments supported by the (k+1)-th LUT with respect to the t segments among all segments supported by the k-th LUT.
3 . The piecewise function approximation method of claim 2 , wherein each of the t segments has an approximation error for the function greater than a preset threshold value, and a number of sub-segments is determined depending on a size of the approximation error of each of the t segments.
4 . The piecewise function approximation method of claim 2 , wherein the mapping information includes, for each of the t segments, a base index indicating a starting position in the (k+1)-th LUT and a number of sub-segments.
5 . The piecewise function approximation method of claim 1 , wherein the k-th LUT includes the approximation coefficients or the mapping information as information on a segment, and a K-th LUT includes the approximation coefficients as information on a segment.
6 . The piecewise function approximation method of claim 1 , wherein extracting the approximation coefficients comprises:
generating a j-th index (being a natural number from 1 to K) based on the input variable value and the mapping information, wherein, when the j-th index is a first index, the first index is generated based only on the input variable value;
extracting a j-th output from a j-th LUT using the j-th index; and
extracting the j-th output as the approximation coefficients when the j-th output is a number in a floating point number system,
wherein extracting the approximation coefficients using the mapping information is repeated when the j-th output is the mapping information.
7 . The piecewise function approximation method of claim 1 , wherein each of the K LUTs assigns the approximation coefficients to a code region used as a number and assigns the mapping information to a code region not used as a number in a floating point number system.
8 . The piecewise function approximation method of claim 7 , wherein, when a sub-normal number code is not used to represent the approximation coefficients, each of the K LUTs assigns the mapping information to the sub-normal number mode region.
9 . The piecewise function approximation method of claim 8 , wherein, for a floating point number representing a number of sub-segments in the mapping information, a non-zero value is set to a mantissa field to indicate the mapping information.
10 . The piecewise function approximation method of claim 8 , wherein, for a floating point number representing the mapping information, a bit value of one preset position in a mantissa field is set to 1 to indicate the mapping information.
11 . The piecewise function approximation method of claim 8 , wherein, for the floating point number representing the mapping information, a preset value is set to a sign field to indicate the mapping information.
12 . A piecewise function approximation device comprising:
a processor; and
memory storing instructions thereon, the instructions when executed by the processor cause the processor to:
obtain an input variable value for a function;
extract approximation coefficients for the function using a multi-level lookup table (LUT) based on the input variable value, the multi-level LUT including K (K being a natural number of 2 or more) LUTs; and
calculate a function value for the input variable value using the approximation coefficients,
wherein the K LUTs support different segment sizes, a segment size supported by a k-th (k being a natural number from 1 to K−1) LUT is greater than a segment side supported by a (k+1)-th LUT, and the (k+1)-th LUT is accessed based on mapping information provided by the k-th LUT.
13 . The piecewise function approximation device of claim 12 , wherein the mapping information is information for dividing each of t segments (t being a natural number) into sub-segments supported by the (k+1)-th LUT with respect to the t segments among all segments supported by the k-th LUT.
14 . The piecewise function approximation device of claim 13 , wherein each of the t segments has an approximation error for the function greater than a preset threshold value, and a number of sub-segments is determined depending on a size of the approximation error of each of the t segments.
15 . The piecewise function approximation device of claim 12 , wherein the instructions cause the processor further to:
generate a j-th index (j being a natural number from 1 to K) based on the input variable value and the mapping information, wherein, when the j-th index is a first index, the first index is generated based only on the input variable value;
determine whether a j-th output extracted from a j-th LUT based on the j-th index is a number in a floating point number system; and
extract the j-th output as the approximation coefficients when the j-th output is the number in the floating point number system,
wherein to extract the approximation coefficients using the mapping information is repeated when the j-th output is the mapping information.
16 . The piecewise function approximation device of claim 12 , wherein each of the K LUTs assigns the approximation coefficients to a code region used as a number and assigns the mapping information to a code region not used as a number in a floating point number system.
17 . A computer-readable recording medium in which instructions are stored, the instructions causing a computer, when executed by the computer, to execute:
obtaining an input variable value for a function;
extracting approximation coefficients for the function using a multi-level lookup table (LUT) based on the input variable value, the multi-level LUT including K (K being a natural number of 2 or more) LUTs; and
calculating a function value for the input variable value using the approximation coefficients,
wherein the K LUTs support different segment sizes, a segment size supported by a k-th (k being a natural number from 1 to K−1) LUT is greater than a segment side supported by a (k+1)-th LUT, and the (k+1)-th LUT is accessed based on mapping information provided by the k-th LUT.