Division and Higher Level Functions



next up previous
Next: MCM Technology Up: Algorithms and Systems Previous: Floating-point Multiplication

Division and Higher Level Functions

 

SNAP has advanced both SRT and functional iteration approaches to division [P12]. In SRT, we have developed techniques for extending the SRT approach to radix 64 division [P15,P30]. We have also shown that improved methods of division by functional iteration are also possible.

Higher-level functions such as square root, logarithm, exponent, and various trig functions are normally performed in software at commensurately much slower speeds. Even if only an approximation to one of these functions is required, a significant amount of time is consumed in producing the result. Occasionally tables are stored in memory to expedite the process of developing either an approximation to, or a starting point for, an algorithm to produce a high-level function or result. These schemes necessarily are limited, as they require growing amounts of table space and still provide limited performance in developing even an approximate result.

Schwarz [P19] has shown that since these functions can generally be represented as a power series (a series of terms involving the powers of the argument of the function), they can be approximated by making special use of the partial product tree of a multiplier. The partial product tree of a multiplier is that portion of a multiplier that sums up 53 multiples of the multiplicand. Each multiple is shifted by a power of two with respect to the other multiples. Thus, the partial product tree represents a sum of 53 terms in a series with the multiplicand being the argument. Schwarz noted that it is possible to enter an argument and, instead of simply replicating it (originally the multiplicand) 53 times by providing modified versions of the argument (ANDed or exclusive-ORed with various constants), we could make approximations to the power series for these high-level functions. The basic manipulations are determined by backsolving an equation that approximates the function to be determined. Using these techniques, it is possible to get an approximation to all of the trig functions as well as the transcendental functions generally accurate to between 11 and 20 bits. This is all accomplished with only a slight increase in multiplier hardware, and it is accomplished in the same time as that to compute a product.



next up previous
Next: MCM Technology Up: Algorithms and Systems Previous: Floating-point Multiplication



Michael Flynn
Tue Dec 13 10:27:47 PST 1994