Computation of power functions using polynomial approximations

• US 7,668,894 B2
• Filed: 08/22/2003
• Issued: 02/23/2010
• Est. Priority Date: 08/22/2003
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Sazegari, Ali, Ollmann, Ian
• Primary Examiner(s): Ngo; Chuong D
• Application Number:
  US10/645,555
• Publication Number:
  US 20050044123A1
• Time in Patent Office: 2,377 Days
• Field of Search: 708/270, 708/276, 708/277, 708/606
• US Class Current: 708/270
• CPC Class Codes: G06F 2207/5523 Calculates a power, e.g. the square, of a number or a function, e.g. polynomials
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

A power function is approximated over an applicable data interval with polynomials determined by means of a Chebyshev minimax approximation technique. In some cases, multiple polynomials may be used to approximate the function over respective ranges of the desirable interval, in a piecewise manner. The appropriate polynomial that approximates the power function over the range of interest is derived and stored. When the power function is to be applied to a particular data value, the data value is first evaluated to determine where it lies within the applicable interval. The constants for the polynomial associated with that range of the interval are then retrieved and used to calculate the power of that data value.

Claims

1. A method for processing a media signal to transform said media signal on a computer system, comprising the steps of:

using a Chebyshev minimax approximation technique to determine, in a processing unit of the computer system, a plurality of polynomials which approximate a mathematical function over a plurality of corresponding data intervals, wherein the length of each interval is individually defined so that the approximation of the function over that interval by its corresponding polynomial has an error less than a predetermined threshold for all of the intervals,

storing the coefficients that define each polynomial in a memory unit of the computer system,

in response to receipt of said media signal, determining, in the processing unit, the interval in which a data value representative of said media signal is located, and retrieving the stored coefficients for the polynomial corresponding to that interval;

evaluating, in the processing unit, the polynomial for the determined interval with said media signal and the retrieved coefficients to thereby transform said media signal; and

outputting said transformed media signal to reproduce said transformed media signal as an output from the computer system, wherein said polynomials and intervals are determined such that the maximum error between said output values and said function is approximately equal for each of said intervals.

2. The method of claim 1, wherein said mathematical function is a power function.

3. The method of claim 1 wherein said media signal is a display signal.

4. The method of claim 1 wherein said media signal is an audio signal.

5. The method of claim 1, wherein said polynomials are of different respective orders, and further including the step of promoting lower-order polynomials to the highest order of the polynomials associated with the retrieved coefficients prior to said evaluating step.

6. A method for generating a media output signal which is based on a power function transformation of a media input signal on a vector processing computer system, comprising the steps of:

determining, in a processing unit of the vector processing computer system, polynomials which respectively approximate said power function over contiguous ranges in a data interval, wherein each range has a length which is individually defined so that the approximation of the power function over that range by its respective polynomial has an error less than a predetermined threshold for all of the ranges;

storing the coefficients that define said polynomials in a memory unit of the vector processing computer system,

in response to receipt of multiple input data values representative of a media signal, determining, in the processing unit, the range in which each data value is located;

retrieving the stored coefficients for each of the determined ranges from the memory unit;

evaluating, in the processing unit, the polynomials whose coefficients are retrieved with the associated input data values in a vectorized manner;

generating, in the processing unit, multiple output values corresponding to said input data values to form digital representations of said media output signal, wherein said polynomials and ranges are determined such that the maximum error between said output values and the power function is approximately equal for each of said ranges; and

reproducing said media output signal from said output values as an output from the computer system.

7. The method of claim 6, wherein said polynomials are determined by means of a Chebyshev minimax approximation technique.

8. The method of claim 6 wherein each of said polynomials is of the same order.

9. The method of claim 6 wherein said polynomials are of different respective orders, and further including the step of promoting lower-order polynomials to the highest order of the polynomials associated with the retrieved coefficients prior to said evaluating step.

10. A vector processing computer system to transform a media signal, comprising:

a memory storing plural sets of coefficients that define a plurality of polynomials which approximate a power function over a plurality of contiguous respective ranges of data values, wherein each range has a length which is individually defined so that the approximation of the power function over that range by its respective polynomial has an error less than a predetermined threshold for all of the ranges;

a vector processing engine that is responsive to receipt of multiple data input values and a command to apply the power function to those input data values, to determine the range in which each data input value is located, to retrieve the set of stored coefficients for each determined range and load them into register locations that respectively correspond to said data input values, to compute multiple output values from said data input values and the loaded coefficients, and to output said output values as a transformed media signal, wherein said polynomials and ranges are determined such that the maximum error between said output values and the power function is approximately equal for each of said ranges; and

an output register from which said output values are retrieved to reproduce said transformed media signal for output from the computer system.

11. A computer-readable medium for a computer system to transform a media signal, the medium containing:

plural sets of coefficients that define respective polynomials which approximate a power function over corresponding ranges in a piecewise manner, wherein each range has a length which is individually defined so that the approximation of the power function over that range by its respective polynomial has an error less than a predetermined threshold for all of the ranges;

an application program that is responsive to receipt of multiple input data values that define a media signal to determine which one of said ranges encompasses each of said input data values, retrieve the set of coefficients that corresponds to each determined range, simultaneously evaluate the polynomials defined by each retrieved set of coefficients with the associated input data values to generate multiple output values at the same time that define an output media signal as a transformed media signal, and reproduce said transformed media signal as an output from the computer system, wherein said polynomials and ranges are determined such that the maximum error between said output values and the power function is approximately equal for each of said ranges.

12. The computer-readable medium of claim 11, wherein each of said polynomials is of the same order.

13. The computer-readable medium of claim 11, wherein said polynomials are of different respective orders, and wherein said program executes the step of promoting lower-order polynomials to the highest order of the polynomials associated with the retrieved coefficients prior to said evaluating step.