Abstract:
An input number is applied to a look-up table that supplies three coefficients based upon certain bits of the input that define a series of bins. The first coefficient is fed directly to an adder that produces the output. The second coefficient is multiplied by a number corresponding to how far the input is from the edge of a bin. This number is then input to the adder that produces the output. The third coefficient is multiplied by a number that is the result of a curve-fit function of a number corresponding to how far the input is from the middle of a bin. This result is then input to the adder that produces the output. These three addends are aligned and summed to produce an output that corresponds within a certain precision of a chosen mathematical function of the input such as the mathematical inverse (1/x) or the mathematical inverse of the square root of the input.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to computer arithmetic. More particularly, this invention relates to a circuit and method for calculating a mathematical function. 
     BACKGROUND OF THE INVENTION 
     One of the primary uses for computers and integrated electronics is to perform large numbers of mathematical operations very quickly. These operations may include mathematical function calculations such as          1   x     ,     1     x       ,                          
     e x , log x, etc. These operations are used in a large number of diverse tasks such as weather forecasting, electronic circuit modeling, beer brewing, and graphics rendering. Unfortunately, the demands being placed on many of these tasks continually pushes the performance of currently available hardware. For example, larger and more complicated weather models lead to weather forecasts that are more accurate. However, if the model doesn&#39;t complete running until after the period it was trying to forecast, the forecast is useless. Accordingly, a smaller, less complicated model is used so that it can complete its forecast in a useful amount of time on the available hardware. Forecasters may want to use the larger more complicated model, but the speed of the hardware prevents the practicality of this. A similar situation exists for many tasks performed by computers and integrated electronics. Therefore, there is a continuing need for faster and better ways to calculate mathematical unctions. 
     SUMMARY OF THE INVENTION 
     An embodiment of the invention utilizes quadratic interpolation to calculate a mathematical function. In a preferred embodiment, the functions          1   x                   and                   1     x                              
     and can be calculated to 24-bit precision from the same hardware. The major components of the hardware to calculate these functions is comprises a look-up table, two Booth-encoded multipliers and a curve-fit function generator. This arrangement allows for fast calculation of the function. This invention is also well adapted to fabrication in monolithic integrated circuits. 
     Calculating a function according to the present invention includes applying the input number to a look-up table that supplies three coefficients based upon certain bits of the input that define a series of bins. This first coefficient is fed directly to an adder that produces the output. The second coefficient is multiplied by a number corresponding to how far the input is from the edge of a bin. This number is then input to the adder that produces the output. The third coefficient is multiplied by a number that is the result of a curve-fit function input with a number corresponding to how far the input is from the middle of a bin. This result is then input to the adder that produces the output. These three addends are aligned and summed to produce an output that corresponds within a certain precision of a chosen function of the input. 
     Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram illustrating the function calculator of the present invention. 
     FIG. 2 is a plot of a function used to help illustrate how values in a look-up table in the preferred embodiment are selected. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 is a block diagram illustrating the function calculator of the present invention. In the preferred embodiment, the input operand, X, is a 24-bit fixed-point number, X[ 23 : 0 ]. It is understood that this number may be the significant of a floating point number the exponent of which may be processed in a manner consistent with the specific function(s) implemented. A number of the highest order bits of X are applied to look-up table  102 . In the preferred embodiment, the highest order 8 bits of X are applied to a 256 entry look-up table,  102 . Look-up table  102  produces three coefficients, A, B, and C. In the preferred embodiment, A is a 23-bit number, A[ 22 : 0 ]. B is a 16-bit number, B[ 15 : 0 ]. And C is a 7-bit number C[ 6 : 0 ]. A is applied directly to a first input of adder  112 . B is applied to multiplier  104 . The output of multiplier  104  is E which is applied to a second input of adder  112 . 
     The other input of multiplier  104  is D[ 15 : 0 ] which is generated by a bitwise inversion of the bits not applied to look-up table  102 . In the preferred embodiment, this is the lower order 16-bits of the input operand. In other words, the bits that are inverted to generate D[ 15 : 0 ] are X[ 15 : 0 ]. In addition, in the preferred embodiment, multiplier  104  is a Booth-encoded multiplier with the least significant carry-in input of the multiplier tied to a logical  1 . Tying the least significant carry-in input of the Booth-encoded multiplier to logical  1 , has the effect of incrementing the input by one least-significant bit. Dropping the higher order bits X[ 23 : 16 ], inverting the rest, and adding a least-significant bit before multiplying, has the effect of generating a two&#39;s-complement of X[ 15 : 0 ] which ends up being equivilent to subtracting X[ 23 : 16 ] from X[ 23 : 0 ]. 
     In the preferred embodiment, multiplier  104  has two 16-bit inputs and a 20-bit output, E[ 19 : 0 ]. A 20-bit output was chosen to minimize the hardware required while still maintaining the monotonicity of the final result considering the function implemented and the precision of the curve-fit function used. 
     The third coefficient, C, is applied to a first input of multiplier  110 . In the preferred embodiment, multiplier  110  has a 10-bit input, a 7-bit input, and a 13-bit output. The third coefficient, C[ 6 : 0 ], is applied to the 7-bit input of multiplier  110 . The second input of multiplier  110  is driven by curve-fit function generator  108 . The output of multiplier  110 , G, is applied to a third input of adder  112 . In the preferred embodiment, G is a 13-bit number, G[ 12 : 0 ]. 
     In the preferred embodiment, curve-fit function generator  108  generates an approximate square of the input number and is implemented as a partial Booth-encoded multiplier. The partial Booth-encoded multiplier has M+1 fewer rows of Booth encoding and shifter-adder rows than a full Booth-encoded multiplier. The missing rows correspond to the M+1 least significant bits. This multiplier is applied to the rows of the partial Booth-encoded multiplier. In addition, the least significant bit of the multiplier (the Mth numbered bit of the original number when counting starts with the 0 th  bit) is applied to the −1 bit input of the first Booth encoder. A multiplicand is generated by removing the Mth numbered bit of the original number, shifting the least significant M bits up by one bit, and placing a zero in the least significant bit position. This multiplicand is applied to the columns of the partial-Booth encoded multiplier to be shifted, added, and subtracted according to Booth&#39;s algorithm. The output of the partial Booth-encoded multiplier array is an approximate square of the input number. This implementation of a curve-fit function generator  108  that generates an approximate square is more fully described in related copending U.S. patent application Ser. No. 09/299,196 which is commonly owned by the assignee of the present document and is hereby incorporated herein by reference in its entirety into this document. This related application is entitled “METHOD AND APPARATUS FOR EFFICIENT CALCULATION OF AN APPROXIMATE SQUARE OF A FIXED-PRECISION NUMBER” and was filed Apr. 23, 1999, now U.S. Pat. No. 6,298,368. 
     An approximation of the square of the input number is used for the curve-fit function in the preferred embodiment. However, other functions and function generation hardware could be used. For example, an exact square function, or a trapezoidal function could be used. To use other functions and hardware, one skilled in the art would realize that appropriate adjustments to the input and output bit sets would be made to achieve a particular desired accuracy, performance, and use of hardware resources. 
     In the preferred embodiment, the input to the curve-fit function generator are the bits not applied to look-up table  102  with the highest order bit of these being inverted and minus lower order bits that are not significant. In the preferred embodiment, this is bits X[ 15 : 5 ] with bit X[ 15 ] being inverted before being applied to the curve-fit function generator as the highest order input bit. Inverting this highest order bit before squaring produces a number that reflects how far from the middle of the range of possible numbers the input number lies. In other words, one-half the largest possible number is subtracted from the input number before squaring. To illustrate by example, take a 6-bit number which would have a range from 0 to 63. If the most significant bit is inverted, then the smallest possible value 000000 2  is translated into 100000 2 =−2 5 =−32. The number very close to the middle of the possible values 100000 2 =32 would be translated into 000000 2 =0 and the number 111111 2 =63 would be translated into 011111 2 =2 5 −1=31. This is the number that is applied to the curve-fit function generator. 
     The three inputs A, E, and G to adder  112  are summed by adder  112  to produce the result, R. In the preferred embodiment R is a 23-bit number R[ 22 : 0 ] reflecting the desired precision of the preferred embodiment. 
     In the preferred embodiment, the function being generated is          F        (   x   )       =       1   x     .                            
     Also, the preferred embodiment is generating the function for the mantissa of an IEEE style normalized format floating point number. Therefore the input number is a 23-bit fixed point number that is greater than or equal to one-half and less than one with the leading “1” bit being implied. Since the input, X, is of the range ½&lt;=X&lt;1 then the output, R, is also of limited range, 1&lt;R&lt;=2. FIG. 2 is a plot of a function used to help illustrate how the values A, B, and C in look-up table  102  are chosen in the preferred embodiment. In FIG. 2, X i  corresponds to the value of the input values applied to look-up table  102 , X[ 23 : 16 ], with zeros assumed for all bits of lesser significance. X i+1  corresponds to the next value of the input values applied to look-up table  102 , X[ 23 : 16 ], with zeros assumed for all bits of lesser significance. For example, if X[ 23 : 16 ] were 00000010 2  (Note: this notation does not show the decimal point or the implied “1” of the normalized format. Also note that the implied “1” does not need to be applied to the look-up table since it never changes.), then X i  would be            1   2     +     1   256       =   0.50390625                          
     and X i+1  would correspond to X[ 23 : 16 ]=00000011 2  which would be            1   2     +     1   256     +     1   512       =     0.505859375   .                            
     Likewise, X i+½  corresponds to the value of X i  with a “1” appended as an additional least significant bit. In other words, if X[ 23 : 16 ] were 00000010 2  then X i+½  would correspond to the value of          000000101   2     =         1   2     +     1   256     +     1   1024       =     0.5048828125   .                              
     Illustrated in FIG. 2 are the factors Δ 1 (X i ), Δ 2 (X i ), and the function F(X). These factors and the value of the function F(X) at X i  are used to determine the coefficients A, B, and C that are stored in look-up table  102  for a particular X i . Solid line  202  illustrates the function F(X) plotted verses X. In the preferred embodiment          F        (   x   )       =       1   x     .                            
     A second embodiment similar to this plot has          F        (   x   )       =       1     x       .                            
     The first coefficient, A, is selected as: A=F(X i )−Δ 2 (X i ). The second coefficient, B, is selected as:        B   =         Δ   1          (     X   i     )       ·       [     1       X     i   +   1       -     X   i         ]     .                              
     The third coefficient, C, is selected as:        C   =         Δ   2          (     X   i     )       ·         [     1       X     i   +     1   2         -     X   i         ]     2     .                              
     The first factor Δ 1 (X i ) is the difference between the function at X i  and X i+1 . In other words, Δ 1 (X i )=F(X i )−F(X i+1 ). The second factor Δ 2 (X i ) is the difference, at X i+½ , between a line drawn between F(X) at X i  and F(X) at X i+1  and F(X). Expressed mathematically, this is:            Δ   2          (     X   i     )       =       [         F        (     X   i     )       +     F        (     X     i   +   1       )         2     ]     -       F        (     X     i   +     1   2         )       .                              
     Although several specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the claims.