Alan H. Karp
Abstract
We present division and square root algorithm for calculations with more bits than are handled by the floating-point hardware. These algorithms avoid the need to multiply two high-precision numbers, speeding up the last iteration by as much as a factor of 10. We also show how to produce the floating-point number closest to the exact result with relatively few additional operations.
- AGARWAL, R. C., COOLEY, J. W., GUSTAVSON, F. G., SHEARER, J. B., SLISHMAN, G., AND TUCKERMAN, B. 1986. New scalar and vector elementary functions for the IBM System/370. IBM J. Res. Dev. 30, 2 (Mar.), 126-144. Google Scholar
Digital Library
- ANSI. 1985. ANSI/IEEE standard for binary floating point arithmetic. Tech. Rep. ANSI/ IEEE Standard 754-1985. IEEE Press, Piscataway, NJ.Google Scholar
- BAILEY, D.H. 1992. A portable high performance multiprecision package. RNR Tech. Rep. RNR-90-022. NASA Ames Research Center, Moffett Field, CA.Google Scholar
- GOLDBERG, D. 1990. Appendix A. In Computer Architecture'A Qualitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA.Google Scholar
- HEWLETT-PACKARD. 1991. HP-UX Reference. 1st ed. Hewlett-Packard, Fort Collins, CO.Google Scholar
- HILDEBRAND, F.B. 1965. Introduction to Numerical Analysis. 2nd ed. Prentice Hall Press, Upper Saddle River, NJ. Google ScholarDigital Library
- KAHAN, W. 1987. Checking whether floating-point division is correctly rounded. Monograph. Computer Science Dept., University of California at Berkeley, Berkeley, CA.Google Scholar
- MARKSTEIN, P. W. 1990. Computation of elementary functions on the IBM RISC System/6000 processor. IBM J. Res. Dev. 34, 1 (Jan.), 111-119. Google ScholarDigital Library
- MONUSCHI, P. AND MEZZALAMA, M. 1990. Survey of square rooting algorithms. IEE Proc. 137, 1, Part E (Jan.), 31-40.Google Scholar
- OLSSON, B., MONTOYE, R., MARKSTEIN, P., AND NGYUENPHU, M. 1990. RISC System~6000 Floating-Point Unit. IBM Corp., Riverton, NJ.Google Scholar
- PATTERSON, D. A. AND HENNESSY, J. L. 1990. Computer Architecture: A Qualitative Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA. Google ScholarDigital Library
Index Terms
- High-precision division and square root
Recommendations
High-Speed Double-Precision Computation of Reciprocal, Division, Square Root and Inverse Square Root
A new method for the high-speed computation of double-precision floating-point reciprocal, division, square root, and inverse square root operations is presented in this paper. This method employs a second-degree minimax polynomial approximation to ...
Power Efficient Division and Square Root Unit
Although division and square root are not frequent operations, most processors implement them in hardware to not compromise the overall performance. Two classes of algorithms implement division or square root: digit-recurrence and multiplicative (e.g., ...
Improving Goldschmidt Division, Square Root, and Square Root Reciprocal
Special issue on computer arithmeticThe aim of this paper is to accelerate division, square root, and square root reciprocal computations when the Goldschmidt method is used on a pipelined multiplier. This is done by replacing the last iteration by the addition of a correcting term that ...
Reviews
James Martin Varah
The authors examine the usual (Newton-Raphson) algorithms for division and for extraction of square roots. These operations are significantly more time-consuming than addition and multiplication, particularly when high precision is desired. The authors show that the costly last step can be speeded up by adjusting the iteration slightly, and this can lead to a significant reduction in the overall execution time of the algorithm. They carefully analyze the accuracy of their algorithm and give the results of extensive testing.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments