Methods and apparatus for determining approximating polynomials using instruction-embedded coefficients

Methods and apparatus for determining approximating polynomials using instruction-embedded coefficients are disclosed. In particular, the methods and apparatus use a plurality of coefficient values stored in a plurality of instructions. The coefficient values are associated with a runtime approximating polynomial of a K-th root family function. The coefficient values and the instructions stored in an instruction memory enable the processor system to determine a K-th root family function approximation value based on the runtime approximating polynomial.

FIELD OF THE DISCLOSURE

The present disclosure relates generally to processor systems and, more particularly, to methods and apparatus for determining approximating polynomials using instruction-embedded coefficients within processor systems.

BACKGROUND

Algebraic and transcendental functions are fundamental in many fields of application. In particular, K-th root family functions of the form (y)±1/K, which include inverse functions, inverse square root functions and square root functions, are performance critical in many graphics applications. Traditional algorithms for these K-th root family functions are typically tailored for desktop computers (e.g., personal computers) and workstation platforms. These traditional algorithms typically provide relatively high precision and accuracy, ranging from approximately seven significant decimals (e.g., IEEE single precision floating point) to sixteen significant decimals (e.g., IEEE double precision floating point). Due to typical accuracy requirements, methods for calculating K-th root family functions usually require data memory accesses, which may require the computers or platforms on which the methods are implemented to have relatively large main memories and data caches.

Many emerging classes of handheld computing platforms such as, for example, handheld platforms based on the Intel® XScale™ processor family, rely heavily on K-th root family function approximation values. In particular, computer graphics capabilities and performance are highly dependent on the performance of the platform responsible for determining K-th root family function approximation values. However, when traditional K-th root family function computational methods are implemented on emerging classes of handheld platforms, these traditional computational methods often result in low and unpredictable performance because data memory accesses often affect the data memory access performance (e.g., corrupt the data cache) of a running application that calls the K-th root family functions.

The data memory access required by traditional methods for determining K-th root family function approximation values is due in part to the fact that these methods generally require function values to be calculated prior to a compilation phase and stored in a table in data memory. In addition, these traditional methods usually employ general polynomials having coefficients that are stored in data memory during a compilation phase.

Alternative methods for determining K-th root family function approximation values that do not require a table of pre-calculated function values have recently been developed. However, these alternative methods typically rely on polynomial functions that include coefficients that are not stored explicitly. Although these alternative methods have provided some improvement over the methods that use pre-calculated function values and tables stored in data memory, the polynomials used by these methods are restrictive and the accuracy of the final result (i.e. the K-th root family function value) is relatively low.

Another method for determining K-th root family function approximation values uses floating-point arithmetic. However, the use of floating-point arithmetic requires software emulation, which may decrease the overall performance of a processor based-platform when processing K-th root family functions.

DETAILED DESCRIPTION

The disclosed methods, apparatus and articles of manufacture may be used to calculate a runtime polynomial associated with a runtime approximating polynomial function of any transcendental or algebraic function. In particular, determining a runtime approximating polynomial function is described herein in connection with a K-th root family function of the form (y)±1/K, where K is an exponent scaling value and may be equal to any relatively small positive integer value (i.e., 1, 2, 3, etc.). The disclosed methods, apparatus and articles of manufacture may be used during a runtime phase within a processor system and may be carried out using only instruction memory accesses (i.e., without requiring data memory accesses). In particular, the examples described herein determine a runtime approximating polynomial by using approximating polynomial coefficient values that are stored in processor instructions during a compilation phase.

Processors such as, for example, processors from the Intel® XScale™ processor family, are capable of processing instructions that include stored coefficients. With these types of processors, an instruction may include an opcode bitfield associated with an executable operation and at least one bitfield associated with a coefficient value. The coefficient value may be used by the processor to execute an operation according to the opcode bitfield. In the case of an Intel® XScale™ processor, an 8-bit coefficient value may be stored within the coefficient bitfield of each instruction. However, the methods, apparatus and articles of manufacture described herein are not limited to processors capable of having only 8-bit coefficient values stored in an instruction, nor are they limited to use with processors from the Intel® XScale™ processor family. To the contrary, the methods, apparatus and articles of manufacture described herein may be used with any processor that supports the use of coefficient values within instructions.

As described in connection with the examples herein, approximating polynomial coefficients may be determined prior to a compilation phase so that during the compilation phase the approximating polynomial coefficients are embedded or otherwise stored in an instruction. For example, a coefficient value 166 may be stored in a multiplication instruction using the following program language.

During a compilation phase, a compiler may compile the above program language and store the coefficient value 166 in a bitfield associated with the multiplication instruction. Additionally, the coefficient value 166 and its associated multiplication instruction may be stored in an instruction memory of a processor system and may be used during a runtime phase. Two example methods for determining approximating polynomial coefficients are described in greater detail in connection withFIGS. 1 and 2. However, other example methods for determining the approximating polynomial coefficients may be used instead.

In addition, the approximating polynomials determined inFIGS. 1 and 2include third-degree polynomials. However, as shown in Equation 1, a polynomial of any degree may be used to approximate any transcendental or algebraic function (e.g., the K-th root family function (y)±1/K).

pA⁡(x)=⁢p0-p1·x+p2·x2-p3·x3+…-⁢pl-1·xl-1+pl·xl≈⁢(y)-1KEquation⁢⁢1
The approximating polynomial pA(x) approximates the K-th root family function (y)±1/K, where y=c0+x for some center of expansion c0. Additionally, the approximating polynomial pA(x) may include a polynomial of any degree as indicated by the value l, to approximate the K-th root family function (y)±1/K.

Approximating polynomial coefficients stored in an instruction may be referred to as instruction-embedded polynomial coefficients. As described in greater detail below in connection withFIGS. 3 and 4, instruction-embedded polynomial coefficients may enable a processor system to determine a runtime approximating polynomial of a K-th root family function (y)±1/Kusing only instruction memory accesses. Furthermore, the processor system may use only instruction memory accesses to determine a K-th root family function approximation value based on the approximating polynomial. Although the apparatus and methods described herein relate generally to K-th root family functions of the form (y)±1/K, instruction-embedded polynomial coefficients may be used to determine any runtime polynomial and runtime polynomial value that approximate any transcendental or algebraic function.

FIG. 1is a flow diagram illustrating an example method for determining and storing approximating polynomial coefficient values. An approximating polynomial of a K-th root family function of the form (y)±1/Kis determined (block110) and coefficients of the approximating polynomial are rounded to eight significant bits (block120) and embedded or otherwise stored in an instruction (block130). The resulting instruction may be stored in an instruction memory (not shown). The approximating polynomial determined at block110may include any number of terms or term coefficients and, thus, may be a second-degree polynomial, a third-degree polynomial, a fourth-degree polynomial, etc. However, the example method for determining and storing approximating polynomial coefficient values is based on a third-degree approximating polynomial.

A K-th root family function approximation value may be determined for any input variable value y within the range 1≦y<2. The input variable value y may be represented in several forms, all of which may include a polynomial variable value x. For purposes of clarity, the input variable value y is represented in two forms below. A first form used to determine an approximating polynomial for an inverse function (y)−1(i.e., K=1), may be written as y=1.5+x, where −0.5≦x<0.5. A second form of the input variable value y, which may be used to determine an approximating polynomial for an inverse square-root function (y)−1/2, may be written as y=1+x, where the polynomial variable value x represents a fractional or decimal portion of the input variable value y. For example, for a value of y equal to 1.3, the input variable value y may be written as y=1+x, where solving for x yields x=0.3.

Generally, an approximating polynomial pa(x) of a K-th root family function (y)±1/Kmay be determined using a minimax approximation. Alternatively, a Taylor series expansion or Chebyshev expansion could be used. A K-th root family function (y)±1/Kis shown in Equation 2 in terms of the polynomial variable x. Furthermore, as shown in Equation 3 below, the approximating polynomial pa(x) may include coefficient values a0through a3.

In Equation 3, the coefficient values a0through a3are used to determine 8-bit approximating polynomial coefficient values. In particular, the coefficient values a0through a3are respectively associated with a zeroth-degree term coefficient value p0, a first-degree term coefficient value p1, a second-degree term coefficient value p2and a third-degree term coefficient value p3. Furthermore, the rounding operation (block120) performed on the coefficient values a0through a3results in two 8-bit values that include the respective coefficient values p0through p3. Additionally, as shown in Equation 4 below, an approximating polynomial p(x) associated with the approximating polynomial pa(x) may include the coefficient values p0through p3.
p(x)=p0−p1·x+p2x2−p3·x3Equation 4
The values or absolute values of the coefficient values p0through p3of Equation 4 may be stored in at least one instruction (block130) during the compilation phase.

As can be seen inFIG. 1, the rounding operation (block120) rounds the coefficient values a0through a3simultaneously. Such a simultaneous rounding operation may reduce the accuracy with which an approximating polynomial approximates the K-th root family function (y)±1/K. Another method described in connection withFIG. 2below may be used to determine the coefficient values p0through p3to more accurately determine an approximating polynomial.

FIG. 2is a flow diagram illustrating another example method for determining approximating polynomial coefficient values. The example method described in connection withFIG. 2may provide a more accurate approximating polynomial of the K-th root family function (y)±1/K. In particular, in contrast to the example method ofFIG. 1, the example method shown inFIG. 2uses independent rounding operations for the coefficient values a0through a3, which results in a more accurate representation of the approximating polynomial.

More specifically, after rounding the coefficient values a0and a1, a second approximating polynomial, which includes a second coefficient value, is determined. After rounding the second coefficient value, a third approximating polynomial that includes a third coefficient value is determined. In this manner, the example method ofFIG. 2ensures greater approximation accuracy when determining an approximating polynomial because each successive coefficient value is based on a previously fixed coefficient value.

Now turning in detail toFIG. 2, a first approximating polynomial to a K-th root family function (y)±1/Kis determined (block210) and is similar to the approximating polynomial pa(x) of Equation 3 above. The first approximating polynomial includes coefficients a0and a1. The zeroth-degree term coefficient p0and the first-degree term coefficient p1are determined by rounding the coefficients a0and a1at block220to 8-bit values. The coefficients p1may be used at block230to determine a second approximating polynomial.

As shown in Equation 5, the first-degree term coefficients p1may be multiplied by the polynomial variable value x, resulting in a product that is subtracted from the inverse square root function of the input variable value y. A second approximating polynomial shown in Equation 6 approximates the function of Equation 5 and is determined at block230.

As shown in Equation 6, the second approximating polynomial includes a coefficient value b2. A second-degree term coefficient value p′2is determined by rounding the coefficient value b2to an 8-bit value (block240).

The second-degree term coefficient p′2may be multiplied twice by the polynomial variable value x, resulting in a product that is subtracted from Equation 5 to produce a function according to Equation 7 below. A third approximating polynomial shown in Equation 8, which approximates the function of Equation 7, is then determined (block250).

As shown in Equation 8, the third approximating polynomial includes a coefficient value g3. A third-degree term coefficient value p′3is determined by rounding the coefficient value g2to an 8-bit value (block260).

Equation 9 below shows an approximating polynomial of the K-th root family function (y)±1/Kincluding the coefficient values p0through p′3.
p(x)=p0−p1·x+p′2·x2−p′3·x3Equation 9
The values or absolute values of the coefficient values p0through p′3of Equation 9 may be stored in at least one instruction (block270) during a compilation. Additionally, the coefficient values p0, p1, p2and p3described in connection withFIG. 1and the coefficient values p0, p1, p′2and p′3described in connection withFIG. 2may be calculated once prior to a compilation phase and used multiple times during a runtime phase to determine a runtime polynomial value. The runtime polynomial value may be associated with a runtime approximating polynomial value of a K-th root family function (y)±1/Kas set forth in greater detail below.

In the following description, the coefficient values p0, p1, p2and p3and the coefficient values p0, p1, p′2and p′3are referred to as the coefficient values p0, p1, p2and p3.

The methods for determining a runtime approximating polynomial value of a K-th root family function (y)±1/Kdescribed below may be implemented on an integer-based processor system as well as a non-integer based processor system (e.g., a floating-point processor system). However, in the case of an integer-based processor system implementation, it may be useful to scale certain values such as, for example, the approximating polynomial coefficient values p0through p3to prevent loss of accuracy, resolution or overflow of subsequently calculated values. For example, if a 32-bit value is to be multiplied by a 10-bit value using a 32-bit operation, it may be useful to first scale the 32-bit value down to a 22-bit value to prevent overflow during the 32-bit multiplication operation.

In addition to scaling, it may also be useful to represent decimal or fractional values as integers when using an integer-based processor system. In particular, the methods described in connection withFIGS. 3 and 4use a Qk notation to represent decimal or fractional values as whole number integers, where the least significant bit of a value is related to 2−k.

In general, the example methods described in connection withFIGS. 3 and 4may be implemented using any integer-based or non-integer-based processor system capable of operations of any bit-length (e.g., 32-bit operations, 64-bit operation, etc.). However, for purposes of clarity, the example methods ofFIGS. 3 and 4are described in connection with a 32-bit integer-based processor system. Thus, scaling methods and Qk notation used in connection with the examples ofFIGS. 3 and 4are based on a maximum bit-length of 32 bits.

FIG. 3is a flow diagram illustrating an example method for determining a runtime approximating polynomial value of an inverse function (y)−1(i.e., K=1) using instruction-embedded polynomial coefficient values. The example method ofFIG. 3includes four instruction-embedded polynomial coefficient values that are generally referred to as a zeroth-degree term coefficient value p0, a first-degree term coefficient value p1, a second-degree term coefficient value p2and a third-degree term coefficient value p3.

During a runtime phase, a processor system (such as that shown inFIG. 6) may perform the example method depicted inFIG. 3to determine a runtime approximating polynomial of an inverse function (y)−1. By performing the operations of blocks305-350during a runtime phase, a runtime approximating polynomial may be used to determine a runtime approximating polynomial value of an inverse function (y)−1. Specifically, the operations performed at blocks305-350reconstruct a runtime approximating polynomial similar to the approximating polynomial p(x) of Equation 4 using the instruction-embedded polynomial coefficient values p0, p1, p2, and p3, the input variable value y, the polynomial variable value x and a series of computational operations.

At runtime, the input variable value y may be provided in Q31format and, as described in connection withFIG. 1, may be represented as y=1.5+x. The polynomial variable value x may be extracted from the input variable value y and formatted (block305) through a series of operations. Performing a 1-bit logical shift left on the input variable value y results in a value y−1 in Q32format. A value of 0.5 is then subtracted from the value y−1 to produce y−1.5, resulting in the polynomial variable value x (i.e., x=y−1.5) in Q32format. A 22-bit arithmetic shift right formats the polynomial variable value x to Q10format.

The third-degree term coefficient value p3may be retrieved from instruction memory and multiplied by the polynomial variable value x (block310), where p3and x may each be represented in Q10format. Multiplying the third-degree term coefficient value p3by the polynomial variable value x results in a product value p3·x in Q20format.

A first-degree polynomial is then determined (block320) by fetching or retrieving the second-degree term coefficient value p2from instruction memory, scaling it to Q20format and subtracting the product value p3·x from the second-degree term coefficient value p2as shown in Equation 10 below.
p2−p3·x  Equation 10
As described below, the first-degree polynomial determined at block320may then be used to determine a second-degree polynomial.

A second-degree polynomial is determined (block340) by retrieving the first-degree term coefficient value p1from instruction memory, formatting p1to Q16format, multiplying the polynomial variable value x, which is in Q10format, by a first-degree polynomial (e.g., the first-degree polynomial shown in Equation 10) and subtracting the result to the first-degree term coefficient value p1. The second-degree polynomial is in Q30format and may be represented as shown in Equation 11 below.
p1−p2·x+p3·x2Equation 11

A runtime approximating polynomial of the inverse function is then determined (block350) by retrieving the zeroth-degree term coefficient value p0from instruction memory, formatting p0to Q14format, multiplying the polynomial variable value x by a second-degree polynomial (e.g., the second-degree polynomial shown in Equation 11) and subtracting the result from the zeroth-degree term coefficient value p0. The subtraction operation results in a runtime approximating polynomial value pv(x) of an inverse function in Q14format and may be evaluated according to Equation 12 below.

u′=pv⁡(x)=p0-p1·x+p2·x2-p3·x3≈11.5+xEquation⁢⁢12
The inverse function (y)−1is shown as 1/1.5+xand is approximated by a runtime approximating polynomial pv(x). The runtime approximating polynomial pv(x) may be used to determine an intermediate inverse function approximation value u′.

In general, if an application is configured to determine a more precise approximation (i.e., more significant bits) of the inverse function (block351), a self-correcting process may be performed at block352on the intermediate inverse function approximation value u′ to determine an inverse function approximation value u having a greater number of significant bits. For example, the intermediate inverse function approximation value u′ may be represented by an 8-bit value, while the inverse function approximation value u may be represented by a more precise 16-bit value. If an application is not configured to determine a more precise value (block351), then the inverse function approximation value u is set equal to the intermediate inverse function approximation value u′.

FIG. 4is a flow diagram illustrating an example method for determining a runtime approximating polynomial value of an inverse square root function and a square root function using instruction-embedded polynomial coefficient values. The instruction-embedded polynomial coefficient values used in this example method generally include the zeroth-degree term coefficient value p0, the first-degree term coefficient value p1and the second-degree term coefficient value p2.

During a runtime phase, a processor system (such as that shown inFIG. 6) may perform the example method depicted inFIG. 4to determine a runtime approximating polynomial of an inverse square root function. A runtime approximating polynomial may be used to determine a runtime approximating polynomial value of an inverse square root function and a square root function, which may be respectively associated with an inverse-square root approximation value and a square root approximation value. An inverse square root approximation value and/or a square root approximation value may be determined during a runtime phase by performing the operations of blocks405-460. Specifically, the operations performed at blocks405-460reconstruct a runtime approximating polynomial similar to the approximating polynomial p(x) of Equation 3 at a runtime phase using the instruction-embedded polynomial coefficient values p0, p1and p2, the input variable value y, the polynomial variable value x and a series of computational operations.

At runtime, the input variable value y may be given as an input value in Q31format and, as described in connection withFIG. 1, may be represented as y=1+x. The polynomial variable value x represents the decimal or fractional portion, which may be extracted from the input variable value y. Isolating the decimal or fractional portion includes performing a 1-bit logical shift left (block405) on the input variable value y, resulting in the polynomial variable value x.

The second-degree term coefficient value p2may be retrieved from instruction memory and multiplied by the polynomial variable value x (block410), where p2and x may each be represented in Q10format. Multiplying the second-degree term coefficient value p2and the polynomial variable value x results in a product value p2·x in Q20format, where the second-degree term coefficient value p2is associated with a runtime invariant value stored in instruction memory and the polynomial variable value x is provided at runtime (i.e., is a runtime variant value).

A first-degree polynomial is then determined (block420) by fetching or retrieving the first-degree term coefficient value p1from instruction memory and scaling it to Q20format and subtracting the product value p2·x from the first-degree term coefficient value p1as shown in Equation 13 below.
p1−p2·x  Equation 13
As shown in Equation 13, the first-degree polynomial determined at block420includes the polynomial variable value x and the approximating polynomial coefficient values p1and p2. As described below, the first-degree polynomial determined at block420may then be used to determine a second-degree polynomial.

As depicted by the example method inFIG. 4, a second-degree polynomial is determined (block440) by multiplying the polynomial variable value x, which is in Q10format, by a first-degree polynomial (e.g., the first-degree polynomial shown in Equation 13). Furthermore, as depicted by Equation 14 below, the second-degree polynomial includes a second-degree term having the second-degree term coefficient value p2and a first-degree term having the first-degree term coefficient value p1.
p1·x−p2·x2Equation 14
The second-degree polynomial shown in Equation 14 may be represented in Q30format and may be used to determine a runtime approximating polynomial of the inverse square root function.

A runtime approximating polynomial of the inverse square root function is determined by retrieving the zeroth-degree term coefficient value p0from instruction memory, formatting p0to Q30format and subtracting a second-degree polynomial (e.g., the second-degree polynomial shown in Equation 14) from the zeroth-degree term coefficient value p0(block440). The subtraction operation results in a runtime approximating polynomial value pv(x) in Q30format that is associated with a runtime approximating polynomial of an inverse square root function.

A runtime approximating polynomial may be used to calculate an intermediate inverse square root approximation value v′ based on the approximating polynomial coefficient values p0, p1and p2and the polynomial variable value x. The intermediate inverse square root approximation value v′ is determined (block450) by performing a rounding operation on the runtime approximating polynomial value pv(x). More specifically, the rounding operation may be used to convert the runtime approximating polynomial value pv(x) in Q30format to a runtime approximating polynomial value pv(x) in Q8format by adding a binary one to the twenty-first bit position of the runtime approximating polynomial value pv(x) and performing a 22-bit logical shift right operation. The runtime approximating polynomial value pv(x) in Q8format includes the intermediate inverse square root approximation value v′ as depicted in Equation 15 below.

v′=pv⁡(x)=p0-p1·x+p2·x2≈11+xEquation⁢⁢15
The inverse square root function of the input variable value y is shown as

11+x
and is approximated by a runtime approximating polynomial that is used to determine the inverse square root approximation value v′.

In general, if an application is configured to determine a more precise approximation (i.e., more significant bits) of the inverse square root function (block451), a self-correcting process may be performed at block452on the intermediate inverse square root approximation value v′. Thus, the self-correcting process (block452) determines the inverse square root approximation value v based on the intermediate inverse square root approximation value v′. If an application is not configured to determine a more precise value (block451), then the inverse square root approximation value v is set equal to the intermediate inverse square root approximation value v′ from block450and control is passed to block455where an application may choose to determine a square root approximation value w.

If an application is not configured to determine a square root approximation value w (block455), then the process may end with the inverse square root approximation value v as a result. On the other hand, if an application is configured to determine the square root approximation value w, then the inverse square root approximation value v is multiplied by the input variable value y (block460) as shown in Equation 16 below.

w=y·v≈(1+x)·11+x=1+xwhere,11+x≈p0-p1·x+p2·x2Equation⁢⁢16
As shown in Equation 16, the square root approximation value w approximates the square root function of the input variable value y (i.e., (y)1/2).

Although the approximation values v and w are depicted as being calculated using 8-bit coefficient values, these values may be calculated using larger bit length values if desired. For example, if the runtime invariant approximating coefficient values p1and p2are stored in instruction memory or retrieved from instruction memory as 16-bit values, a 16-bit value may be calculated at block450that includes the intermediate inverse square root approximation value v′.

One example method that may be used for retrieving 16-bit coefficient values from memory includes separating a 16-bit coefficient into two 8-bit values and storing each of the 8-bit values in a different instruction during a compilation phase. The instructions may be sequenced so that during a runtime phase, each 8-bit value that is stored in a different instruction may be easily concatenated to form a 16-bit coefficient. This method for retrieving coefficients having more than eight bits from instruction memory during runtime may be used for any number of coefficients having any desired bit length. Coefficients having more than eight bits may be implemented by using a processor system that supports having larger bit-length values stored in instructions.

FIG. 5is a flow diagram that depicts an example method for performing a self-correcting process that may be used to determine a function approximation value based on an intermediate function approximation value. In general, the self-correcting process may be used to determine a function approximation value f (i.e., a K-th root family function approximation value of the K-th root family function (y)±1/K) that includes a more precise representation of the intermediate function approximation value f′. For example, the intermediate function approximation value f′ may be an 8-bit value. However, by performing the self-correcting process on the intermediate function approximation value f′, a more precise value may be determined, such as, for example, a 16-bit value that includes the function approximation value f. The intermediate function approximation value f′ is associated with the intermediate approximation values u′ and v′ ofFIGS. 3 and 4. For example, if an application is configured to determine the inverse square root approximation value v, then the intermediate function approximation value f′ is set equal to the intermediate inverse square root function approximation value v′ and the resulting function approximation value f includes the inverse square root approximation value v.

The self-correcting process shown inFIG. 5may be used to determine the function approximation value f based on the intermediate function approximation value f′ and the input variable value y. For purposes of clarity, the intermediate function approximation value f′ is depicted as being based on the intermediate inverse square root approximation v′. However, the self-correcting process may also be performed on the intermediate inverse function u′ described in connection withFIG. 3or any K-th root family function (y)±1/K.

The intermediate function approximation value f′ may be mathematically represented in terms of an inverse square root function of the input variable value y as set forth in Equation 17 below. Alternatively, the intermediate function approximation value f′ may be more precisely represented in terms of the inverse square root function of the input variable value y and an error approximation value e as set forth in Equation 18 below.

As shown in Equation 17, the intermediate function approximation value f′ is approximately equal to the inverse square root function of the input variable value y. Alternatively, Equation 18 shows that the intermediate approximation value f′ may be equal to the inverse square root function of the input variable value y multiplied by a quantity 1+e. The error approximation value e is associated with an approximation factor introduced by determining the intermediate approximation value f′ using an approximating polynomial value (e.g., the approximating polynomial value pv(x) of Equation 15). Persons of ordinary skill in the art will readily appreciate that the self-correcting process may be used to reduce the effect of the error approximation value e on the function approximation value f.

As depicted inFIG. 5, the intermediate function approximation value f′ is raised to the power of the exponent scaling value K (block510). The value of K is equal to two in the case of the intermediate inverse square root approximation value v′. Thus, the operation at block510determines a scaled intermediate function approximation value f′2, which is alternatively shown in Equation 19 below. The scaled intermediate function approximation value f′2is multiplied by the input variable value y (block520) to determine a product value f′2·y as shown in Equation 20 below.

Next, an arithmetic shift operation (block530) may be performed to format the product value f′2·y to an appropriate bit-length for subsequent mathematical operations. An arithmetic shift operation is used to preserve the sign-bit of the Q32format signed product value f′2·y. In particular, the arithmetic shift operation is performed as an 11-bit arithmetic shift right operation, which results in a product value f′2·y in Q21format.

The product value f′2·y, which is in Q21format, is multiplied by the intermediate function approximation value f′, which is in Q9format, at block540, resulting in a product value f′3·y in Q30format. The product value f′3·y is then divided by the exponent scaling value K (block543). The value of K is equal to two for the intermediate inverse square root approximation value v′. Thus, the operation at block543determines a scaled product value

f′3·y2,
which may be formatted in Q30format. A 22-bit logical shift left operation is performed on the intermediate function approximation value f′ (block545) after which the product value

f′3·y2
in Q30format is subtracted from the resulting intermediate function approximation value f′ (block550). The subtraction operation at block550results in a 16-bit value in Q30format that includes the function approximation value f. The function approximation value f includes the inverse square root approximation value v. Additionally, as a result of the self-correcting process, the inverse square root approximation value v is represented with greater precision (i.e., a 16-bit value) than the intermediate inverse square root approximation value v′ (i.e., an 8-bit value determined at blocks405-450ofFIG. 4).

Although a 16-bit function approximation value f may be determined using the methods described in connection withFIG. 5, a function approximation value f having more significant bits (i.e., of greater precision) may be used instead. In particular, the function approximation value f may be determined to a precision equivalent to the input variable value y and/or the polynomial variable value x provided inFIGS. 3 and 4. For example, on a 64-bit processor system a 64-bit input variable value y may be used to enable the methods ofFIGS. 3,4and5to determine a 64-bit function approximation value f.

Additionally, multiple iterations of the self-correcting process described in connection withFIG. 5may be performed to increase the precision of the function approximation value f. For example, for a 32-bit input variable value y, the methods ofFIGS. 3 and 4may be used to determine an 8-bit intermediate function approximation value f′. However, a 32-bit function approximation value f may be determined by performing two iterations of the self-correcting process on the 8-bit intermediate function approximation value f′. Each iteration of the self-correcting process increases the precision of the function approximation value f by a factor of two.

FIG. 6is a block diagram of an example processor system610that may be used to implement the apparatus and methods described herein. As shown inFIG. 6, the processor system610includes a processor612that is coupled to an interconnection bus or network614. The processor612includes a register set or register space616, which is depicted inFIG. 6as being entirely on-chip, but which could alternatively be located entirely or partially off-chip and directly coupled to the processor612via dedicated electrical connections and/or via the interconnection network or bus614. The processor612may be any suitable processor, processing unit or microprocessor such as, for example, a processor from the Intel X-Scale™ family, the Intel Pentium™ family, etc. In the example described in detail below, the processor612is a thirty-two bit Intel processor, which is commonly referred to as an IA-32 processor. Although not shown inFIG. 6, the system610may be a multi-processor system and, thus, may include one or more additional processors that are identical or similar to the processor612and which are coupled to the interconnection bus or network614.

The processor612ofFIG. 6is coupled to a chipset618, which includes a memory controller620and an input/output (I/O) controller622. As is well known, a chipset typically provides I/O and memory management functions as well as a plurality of general purpose and/or special purpose registers, timers, etc. that are accessible or used by one or more processors coupled to the chipset. The memory controller620performs functions that enable the processor612(or processors if there are multiple processors) to access a system memory624, which may include any desired type of volatile memory such as, for example, static random access memory (SRAM), dynamic random access memory (DRAM), etc. The I/O controller622performs functions that enable the processor612to communicate with peripheral input/output (I/O) devices626and628via an I/O bus630. The I/O devices626and628may be any desired type of I/O device such as, for example, a keyboard, a video display or monitor, a mouse, etc. While the memory controller620and the I/O controller622are depicted inFIG. 6as separate functional blocks within the chipset618, the functions performed by these blocks may be integrated within a single semiconductor circuit or may be implemented using two or more separate integrated circuits.

The methods described herein may be implemented using instructions stored on a computer readable medium that are executed by the processor612. The computer readable medium may include any desired combination of solid state, magnetic and/or optical media implemented using any desired combination of mass storage devices (e.g., disk drive), removable storage devices (e.g., floppy disks, memory cards or sticks, etc.) and/or integrated memory devices (e.g., random access memory, flash memory, etc.).

Although certain methods, apparatus and articles of manufacture have been described herein, the scope of coverage of this patent is not limited thereto. To the contrary, this patent covers all methods, apparatus and articles of manufacture fairly falling within the scope of the appended claims either literally or under the doctrine of equivalents.