Hardware starting approximation method and its application to the square root operation
Authors:
- E.M. SchwarzESE.M. Schwarz
- M.J. FlynnMFM.J. Flynn
- 1 January 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 45 (12) , 1356-1369
Abstract
Quadratically converging algorithms for high-order arithmetic operations typically are accelerated by a starting approximation. The higher the precision of the starting approximation, the less number of iterations required for convergence. Traditional methods have used look-up tables or polynomial approximations, or a combination of the two called piecewise linear approximations. This paper provides a revision and major extension to our study [1] proposing a nontraditional method for reusing the hardware of a multiplier. An approximation is described in the form of partial product array (PPA) composed of Boolean elements. The Boolean elements are chosen such that their sum is a high-precision approximation to a high-order arithmetic operation such as square root, reciprocal, division, logarithm, exponential, and trigonometric functions. This paper derives a PPA that produces in the worst case a 16-bit approximation to the square root operation. The implementation of the PPA utilizes an existing 53 bit multiplier design requiring approximately 1,000 dedicated logic gates of function, additional repowering circuits, and has a latency of one multiplication.Keywords
This publication has 19 references indexed in Scilit:
- Parallel high-radix nonrestoring divisionIEEE Transactions on Computers, 1993
- Cost-efficient high-radix divisionJournal of Signal Processing Systems, 1991
- Hard-wired multipliers with encoded partial productsIEEE Transactions on Computers, 1991
- Design of the IBM RISC System/6000 floating-point execution unitIBM Journal of Research and Development, 1990
- Minimum relative error approximations for 1/tNumerische Mathematik, 1989
- Boolean Functions1989
- Some Properties of Iterative Square-Rooting Methods Using High-Speed MultiplicationIEEE Transactions on Computers, 1972
- Starting approximations for square root calculation on IBM system /360Communications of the ACM, 1966
- High-Speed Arithmetic in Binary ComputersProceedings of the IRE, 1961
- A SIGNED BINARY MULTIPLICATION TECHNIQUEQuarterly Journal of Mechanics and Applied Mathematics, 1951