High-radix algorithms for high-order arithmetic operations
Eric M. Schwarz · 1993
Many common algorithms for high-order arithmetic operations require an initial approximation. The Newton-Raphson algorithm starts with an approximation and then quadratically converges on the solution. The initial approximation determines the number of iterations of the algorithm and is typically implemented as a look-up table in the form of a ROM or PLA. A novel method is suggested which describes high-order arithmetic operations with a partial product array. This method applies to the operations of division, reciprocal, square root, natural logarithm, exponential, and trigonometric functions. The partial product array of Boolean elements which describes the operation can be summed on an existing floating-point multiplier. The hardware needed is only the logic gates to create the Boolean elements in the array and a multiplexor, and the latency is that of the multiplier. Thus, by reusing a floating-point multiplier, a high-precision approximation to a high-order arithmetic operation can be implemented with a low marginal cost. This dissertation describes the implementation and shows a method for deriving partial product arrays to approximate arithmetic operations. Then the proposed method is applied and evaluated for several operations. The proposed method yields a minimum approximation of twelve bits correct for the reciprocal operation and sixteen bits for the square root operation. The proposed method is shown to be as small as 0.05% the size (in gates) of an equivalent precision look-up table and has up to four times the accuracy (in bits) as an equivalent latency polynomial approximation. Also, three new iterative algorithms to increase the precision of the approximations and a theoretical analysis of the partial product array representation are detailed. Thus, high-radix algorithms of many arithmetic operations are possible at low cost.