Abstract:
An approximation circuit approximates a function f(x) of an input value “x” by adding at least the first two terms in a Taylor series (i.e., f(a) and f′(a)(x−a)) where “a” is a number reasonably close to value “x”. The first term is generated by a first look-up table which receives the approximation value “a”. The first look-up table generates a function f(a) of the approximation value “a”. The second look-up table generates a first derivative f′(a) of the function f(a). A first multiplier then multiplies the first derivative f′(a) by a difference (x−a) between input value “x” and approximation value “a” to generate a product f′(a)(x−a). The approximation circuit can approximate the function f(x) by adding the third term of the Taylor series, (½)f″(a)(x−a) 2 .

Description:
BACKGROUND OF THE INVENTION 
     Functional approximation circuits, such as reciprocal approximation circuits, are known in the art. For example, a division (e.g., in 2D and 3D graphics implementations) is typically implemented using a reciprocal approximation circuit. The resulting reciprocal approximation of the divisor is multiplied with the dividend, thereby emulating the divide operation. 
     A conventional reciprocal approximation circuit uses an iterative method (e.g., the Newton-Raphson method) based on an initial estimate. Reciprocal approximations are fed back through the circuit until a reciprocal approximation of a desired precision is obtained. This iterative process takes significant time. Thus, a faster circuit and method for approximating, for example, a reciprocal are desired. 
     SUMMARY OF THE INVENTION 
     An approximation circuit approximates a function f(x), given an input value “x”, by computing and adding at least the first two terms in a Taylor series (i.e., f(a) and f′(a)(x−a)) where “a” is an approximation value reasonably close to the input value “x”. For example, “a” may share the most significant bits of input value “x”. The values f(a) and f′(a) can be provided by look-up tables. A first look-up table receives the approximation value “a”, and provides a function f(a). Similarly, a second look-up table receives the approximation value “a” and provides a first derivative f′(a) of the function f(a). A multiplier then multiplies the value f′(a) represented by the bits generated by the second look-up table by a difference (x−a) between value “x” and value “a”. An adder adds the first term represented by the bits generated by the first look-up table and the second term represented by the bits generated by the multiplier to provide an approximation of f(x). 
     In one embodiment, the third term (i.e., (½)f″(a)(x−a) 2 ) of the Taylor series is also computed. For example, a third look-up table receives the approximation value “a” and provides a value of one half of the second derivative (½)f″(a) of the function f(a). A fast squaring circuit receives the difference (x−a) and generates bits representing the square (x−a) 2 . Another multiplier receives the value (½)f″(a) and the value (x−a) 2  to generate the third term (½)f″(a)(x−a) 2 . 
     Since the terms of the Taylor series are computed in parallel, an adder adds all the terms simultaneously to obtain the approximation. Since no iteration is performed, the approximation circuit of the present invention is faster than conventional approximation circuits. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a diagram of an approximation circuit according to the present invention. 
     FIG. 2 is a diagram of the squaring circuit of FIG.  1 . 
     FIG. 3 is a diagram of hexadecimal values entered into the left-most look-up table of FIG.  2 . 
     FIG. 4 is a diagram of hexadecimal values entered into the middle look-up table of FIG.  2 . 
     FIG. 5 is a diagram of hexadecimal values entered into the right-most look-up table of FIG.  2 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The following description contains references to several drawings which contain the same or similar elements. Throughout this description, the same or similar elements in different drawings are identified with the same reference symbols. 
     FIG. 1 schematically shows an approximation circuit  100  according to an embodiment of the present invention. The approximation circuit  100  does not operate iteratively. 
     The following Equation (1) shows the first three terms in a Taylor series. 
     
       
           f ( x )≅ f ( a )+ f ′( a )( x−a )+(½) f ″( a )( x−a ) 2   (1) 
       
     
     where, 
     “x” is the input value, 
     f(x) is the function of “x” to be approximated, 
     “a” is an approximation value reasonably close to “x”, 
     f(a) is the function of “a”, 
     f′(a) is the first derivative of f(a), and 
     f″(a) is the second derivative of f(a). 
     For example, for reciprocal approximations, f(x) is x −1 . The Taylor series approximation for x −1  is provided in Equation (2). 
     
       
           x   −1   −a   −1   −a   −2 ( x−a )+ a   −3 ( x−a ) 2   (2) 
       
     
     Approximation circuit  100  calculates these first three terms of the Taylor series in parallel and thus is faster than circuits using the iterative Newton-Raphson approach. 
     In operation, approximation circuit  100  receives 32-bits x[ 8 :− 23 ] representing an input value “x”. Throughout this description, an example of a value represented by bits x[ 8 :− 23 ] is positive 0.698781251907310 10 ×2 108 . 
     Bit x[ 8 ] (e.g., 0) represents the sign (e.g., non-negative) of the input value “x”. Bits x[ 7 : 0 ] (e.g., 011,01100.=108 10  signed) represent the exponent of the input value “x” in two&#39;s complement format. Bits x[ 1 :− 23 ] e.g., 0.10110,01011,10001,10101,010=0.6987812519073 10 ) represent the mantissa of input value “x”. The exponent bits x[ 7 : 0 ] are such that bit x[− 1 ] always has a binary one value. 
     Approximation circuit  100  approximates the reciprocal x −1  of input value “x”. In this description, for the mantissa, nomenclature [m:n] is used to indicate a series of contiguous bits having weights ranging from 2 m  down to 2 n . For example, mantissa x[− 1 :− 23 ] represents 23 bits ranging from bit x[− 1 ] having weight 2 −1  down to bit x[− 23 ] having weight 2 −23 . Also for clarity, commas are placed every five binary bits from the binary decimal point. 
     Referring to Equation (2), approximation value “a”, represented by bits x[− 1 :− 8 ], has 128 possible values ranging from 0.10000,000 to 0.11111,111 (e.g. 0.10110,010=0.6953125 10 ). Value (x−a), represented by bits x[− 9 :− 23 ], has 2 15  possible values ranging from 0.00000,00000,00000,00000,000 to 0.00000,00011,11111,11111,111 (e.g., 0.00000,00011,10001,10101,010=0.003468751907349 10 ), 
     Referring to FIG. 1, look-up tables  102 ,  104  and  106  each receives input bits x[− 1 :− 8 ] (e.g., 0.10110,010). In this embodiment, each of look-up tables (LUTs)  102 ,  104  and  106  holds 128 entries. A suitable implementation for each of LUTs  102 ,  104  and  106  is logic circuitry. Another suitable implementation for each of LUTs  102 ,  104  and  106  is a memory device such as read-only memory (ROM) or random-access memory (RAM). 
     (a −1 ) The First Term of Equation (2) 
     LUT  102  generates a 26-bit precision unsigned approximation a −1 [ 0 :− 25 ] of the first term a −1  (e.g., 1.01110,00000,10111,00000,10000≅1.438202381134 10 ) where 1&lt;a −1 ≦2. The term a −1 [ 0 :− 25 ] is sign extended with zero&#39;s to form a 29-bit first term a −1 [ 3 :− 25 ] (e.g., 0001.01110,00000,10111,00000,10000) 
     [−a −2  (x−a)] The Second Term of Equation (2) 
     LUT  104  generates an 18-bit precision approximation −a −2 [ 2 :− 15 ] of −a −2  (e.g., 101.11101,11001,11111=−2.068389892578 10 ) in two&#39;s complement format where − 4  &lt;−a −2 &lt;− 1 . A floating point multiplier  114  receives and multiplies input values −a −2 [ 2 :− 15 ] and x[− 9 :− 23 ] (i.e., x−a) to generate the second term [−a −2 (x−a)][− 6 :− 38 ] (e.g., .*****,11000,10100,11100,10111,11110,11010,110=−0.007174731385022 10 ). Asterisks “*” are used to show the weight relationship of bits [−a −2  (x−a)][− 6 :− 37 ] with respect to the binary decimal point. Multiplier  114  discards the 13 least significant bits and sign extends back to a 29-bit value [−a −2  (x−a)][ 3 :− 25 ] (e.g., 1111.11111,11000,10100,11100,10111=−0.007174760103226 10 ). 
     [a −3  (x−a) 2 ] The Third Term of Equation (2) 
     LUT  106  generates a 12-bit precision approximation a −3 [ 3 :− 8 ] of a −3  (e.g., 0010.11110,011)=2.94921875 10 ) where 1≦a −3 &lt;8. A squaring circuit  108  receives and squares the twelve most significant bits of x[− 9 :− 23 ] (i.e., x−a) to generate [(x−a) 2 ][− 17 :− 40 ] (e.g., .*****,*****,*****,*1100,10011,10101,10111,11001=0.00001203058582178 10 ). The least significant 9-bits of the square [(x−a) 2 ][− 17 :− 40 ] are discarded to form [(x−a) 2 ][− 17 :− 31 ] (e.g., .*****,*****,*****,*1100,10011,10101,1=0.0000120303593576 10 ). A floating point multiplier  116  receives and multiplies input values a −3 [ 3 :− 8 ] and [(x−a) 2][−17:−31] to generate the third term [a   −3  (x−a) 2 ][ 13 :− 39 ] (e.g., .*****,*****,**001,00101,00110,10000,10001,0001=0.00003548016138666 10 ). The lower 14 bits of this product are discarded and the third term is sign extended to 29-bits to form [a −3  (x−a) 2 ][ 3 :− 25 ] (e.g., 0000.00000,00000,00001,00101,00110=0.00003546476364136 10 ). 
     Addition of Terms 
     The three terms are added in adder  122  to generate preliminary sum PS[ 3 :− 25 ]. A text book addition for the example values provided above is as follows. 
     a −1  0001.01110,00000,10111,00000,10000 
     −a −2  (x−a) 1111.11111,11000,10100,11100,10111 
     a −3  (x−a) 2  +0000.00000,00000,00001,00101,00110 
     PS[ 3 :− 25 ] 0001.01101,11001,01101,00010,01101 
     Normalizer  130  uses the lower three bits PS[− 23 :− 25 ] to round bit PS[− 22 ], and a right shift occurs. The resulting bits that have weights less than unity form the reciprocated mantissa R[− 1 :− 23 ] (e.g., 0.10110,11100,10110,10001,010=0.7155315876007 10 ). Normalizer generates a binary one carry out bit “c” to increment the exponent to compensate for the right shift. 
     Exponent 
     The reciprocal of the exponent is the negative of the exponent. However, a binary one value must be added to the negated exponent to account for the right shift of the mantissa. Accordingly, exponent unit  140  inverts all bits x[ 7 : 0 ], increments once to obtain −x[ 7 : 0 ], and increments once again in response to signal “c” to compensate for the right shift in the mantissa to obtain reciprocated exponent bits R[ 7 : 0 ] (e.g., 100,10101=−107 10 ) representing the exponent of the value “x” in two&#39;s complement format. 
     Sign 
     Reciprocating a number does not change its sign. Thus, the sign bit R[ 8 ] representing the sign of the reciprocated value is made equal to the sign bit x[ 8 ] of the input value “x”. 
     Thus, reciprocal approximating circuit  100  approximates the reciprocal of x[ 8 :− 23 ] to be R[ 8 :− 23 ] (e.g., approximates the reciprocal of positive 0.6987812519073×2 108  to be positive 0.7155315876007×2 −107 ). The correct reciprocal to 13 digits of base ten precision is 0.7155315037936×10 −107 . Thus, the mantissa is accurate to 6 or 7 base ten digits of precision. 
     Approximation circuit  100  is quite fast because look-up tables  102 ,  104  and  106  take little time to generate bits representing f(a), f′(a) and (½) f″(a), respectively. Two relatively fast floating point multipliers  114  and  116  multiply terms in parallel. Normalization in normalizer  130  and determination of the reciprocated exponent in exponent unit  140  are also quite efficient. On the other hand, conventional squaring circuits are typically slower than look-up tables. 
     Squaring Circuit  108   
     Squaring circuit  108  may be a novel squaring circuit such as that disclosed in co-pending United States patent application Ser. No. 09/138,301 filed Aug. 21, 1998, entitled “A Circuit and Method for Fast Squaring by Breaking the Square into a Plurality of Terms”, which is incorporated herein by reference in its entirety. 
     FIG. 2 is a detailed block diagram of squaring circuit  108  of FIG.  1 . Squaring circuit  108  receives bits x[− 9 :− 20 ], of which left hand squaring circuit  210  receives bits x[− 9 :− 14 ] (e.g., .*****,***11,1000=0.00341796875 10 ), right hand squaring circuit  220  receives bits x[− 15 :− 20 ] (e.g., bits .*****,***,****1,10101=0.00005054473876953 10 ), and multiplier  230  receives all bits x[− 9 :− 20 ]. 
     Squaring circuit  210  generates bits L 2 [− 17 :− 28 ] (e.g., .*****,*****,*****,*1100,01000,000=0.00001168251037598 10 ) representing the square of value x[− 9 :− 14 ]. Squaring circuit  220  generates bits R 2 [− 29 :− 40 ] (e.g., .*****,*****,*****,*****,****,***10,10111,11001=0.00000000255477061728 10 ) representing the square of value x[− 15 :− 20 ]. The two values L 2 [− 17 :− 28 ] and R 2 [− 29 :− 40 ] are concatenated to form concatenated bits L 2 O(R 2 [− 17 :− 40 ] (e.g., .*****,*****,*****,*1100,01000,00010,10111,11001=0.00001168506514659 10 ). 
     Multiplier  230  performs a multiplication of the values represented by bits x[− 9 :− 14 ] and bits x[− 15 :− 20 ] by, for example, a conventional “Wallace Tree” technique, and performs a left shift to generate bits LRs[− 22 :− 33 ] (sum term) and LRc[− 22 :− 33 ] (carry term). Together, the terms LRs[− 22 :− 33 ] and Lrc[− 22 :− 33 ] represent twice the product of x[− 9 :− 14 ] and x[− 15 :− 20 ] (e.g., in the exemplary embodiment, the sum of LRs[− 22 :− 33 ] and LRc[− 22 :− 33 ] should be .****,********,****,*1011,10011,000=0.0000003455206751823 10 ). 
     Squaring circuit  108  is faster than conventional squaring circuits and generates a square about the same time as the look-up tables  102 ,  104  and  106  generate results. 
       3 : 1  adder  240  adds values L 2 ∥R 2 [− 17 :− 40 ] LRs[− 22 :− 33 ] and LRc[− 22 :− 33 ] (with appropriate extensions to match weights) to obtain the square [(x−a) 2 ][− 17 :− 40 ] .*****,*****,*****,*1100,10011,10101,10111,11001=0.00001203058582178 10 ). The nine least significant bits of [(x−a) 2 ][− 17 :− 40 ] are discarded so that squaring circuit  108  outputs bits [(x−a) 2 ][− 17 :− 31 ] 
     Although the above approximation circuit is described as approximating a reciprocal of the input value “x”, one skilled in the art will recognize that approximation circuit  100  may estimate any function (e.g., x −3 , x ½ ) of input value “x” by using different entries in the look-up tables  102 ,  104  and  106 . 
     Although the first three terms of a Taylor series are used above, approximation circuit  100  may also only calculate and add the first two terms of the series. In this case, LUT  106 , squaring circuit  108 , and multiplier  116  are not used. 
     The above describes reciprocal approximation using Taylor series constants a −1 , −a −2  and a −3 . However, note that the values (hereinafter, K 1 , K 2  and K 3 ) stored for a −1 , −a −2  and a in LUT  102 , LUT  104  and LUT  106  differ from the best representable approximation of the values a −1 , −a −2  and a −3 , respectively. As an illustration, in the above example, approximation value “a” is 0.10110,010 (0.6953125 10 ). The actual value for a −1  to 13 significant digits is 1.438202247191. The binary value K 1  stored in LUT  102  for a −1  is 1.01110,00000,10111,00000,10000 (1.438202381134 10 ). However, the binary value 1.01110,00000,10111,00000,01100 (1.438202261925 10 ) is closer to the actual value for a −1 . 
     For reciprocal approximation using approximation circuit  100 , the accuracy of the final result R[ 8 :− 23 ] is improved by one or two digits of precision if the constants K 1 , K 2  and K 3  stored in LUT  102 , LUT  104  and LUT  106  are perturbed slightly from the best approximation of the Taylor series constants a −1 , a −2 , and a −3 , respectively. For some functions, the variance from the Taylor series constants may be significant. 
     For each possible approximation value “a”, the values K 1 , K 2  and K 3  were varied with the aim of maximizing the accuracy of the result R[ 8 :− 23 ] within the whole range of input values “x” represented by that approximation value “a”. 
     For example, all input values “x” from 0.5 to 0.50390624 are approximated with approximation value 0.5. When the input value “x” is relatively close to approximation value “a”, the first three terms of the Taylor series would give a fairly accurate result R[ 8 :− 23 ]. However, if the input value “x” is towards the upper limit of the range, 0.50390624, the result R[ 8 :− 23 ] is much less precise if accurate Taylor constants are used. Thus, to reduce the maximum error within the range of 0.5 to 0.50390624, constants K 1 , K 2  and K 3  located within look-up tables  102 ,  104  and  106  are chosen to be other than the constants a −1 , −a −2  and a −3  expected under a pure Taylor series. For example, K 1  may be 2.000001 hexadecimal (2.000000059605) instead of 2, K 2  may be FC.000A hexadecimal (−3.999847412109) instead of −4, and K 3  may be 7.E800 hexadecimal (7.90625) instead of 8. These values were obtained by simulating the approximation circuit  100  described above for many candidate values of K 1 , K 2  and K 3  and varying “x” within the range of 0.5 to 0.50390624 in order to find the values of K 1 , K 2  and K 3  that minimize the maximum approximation error within that range. This custom selection of the constants K 1 , K 2  and K 3  for each range of x allows for precision of 1 or 2 bits of precision more accurate than obtainable by using the values of the Taylor series constants a −1 , −a −2  and a −3 . 
     Values for K 1 , K 2  and K 3  found to maximize accuracy for each approximation value “a” are shown respectively in FIG. 3, FIG.  4  and FIG.  5 . Approximation values “a” are shown to the right of “,//” for each column. Input value “a” of 0.10000,000 is represented by term 0x00, 0.10000,001 is represented by term 0x01 and so forth until 0.11111,111 is represented by term 0x7F. The value to the left of “,//” represents the look-up table values. 
     In FIG. 3, 0x002000001 represents 2.000001 hexadecimal (2.000000059605 10 ) which is the value K 1  in LUT  102  for an approximation value “a” of 0.10000,000. Thus, the values to the left of “,//” in FIG. 3 have a least significant hexadecimal digit of weight 2 −24 . 
     In FIG. 4, 0xfffc000a is a hexadecimal representation, in two&#39;s complement format, of K 2  for an approximation value “a” of 0.10000,000. The least significant hexadecimal bit has a weight 2 −16 . Thus 0xfffc00a represents two&#39;s complement binary 100.00000,00000,00101,0 (−3.999847412109 10 ). 
     In FIG. 5, 0xfd0 is a hexadecimal representation of K 3  for an approximation value “a” of 0.10000,000. The least significant hexadecimal bit has a weight 2 −9 . Thus 0xfd0 represents binary 111.11101,0000 (7.90625 10 ). 
     The embodiments described above are illustrative only and not limiting. In light of this disclosure, various substitutions and modifications will be apparent to one of ordinary skill. Therefore, the present invention is defined by the following claims.