Evaluation of the square root function on microprocessors

ABSTRACT

The software requirements for real time applications of microprocessors have received little attention from the scientific community, Efficient algorithms for the evaluation of special functions for such purposes are needed, however, The aim of this paper is to report on initial efforts to develop software for evaluation of the square root function in microprocessors utilizing fixed point computation. Numerical results of the performance of these algorithms are described for both eight and sixteen bit precision machines.

REFERENCES

• 1: A.V.Oppenheim and C.U.Weinstein, Effects of Finite Register Length in Digital Filtering and the Fast Fourier Transform, Proc. IEEE, Vol. 60, pp. 957-975, Aug. 1972.
• 2: F.F.Kuo and J.F.Kaiser, eds., System Analysis by Digital Computer, Wiley and Sons, Inc., New York, 1966.
• 3: L.P.Mulcahy, Statistical Analysis of Digital Fixed-Point Multiplication Errors, Naval Undersea Research and Development Center, San Diego, NUC-TP-254, AD 735-460, Dec., 1971.
• 4: W.T.Bennet, Spectra of Quantized Signals, Bell System Technical Journal, Vol. 27, pp. 446-472, July, 1948.
• 5: J.E.Shaver, Topics in Statistical Quantization, Stanford Electronics Lab, Stanford, California, SEL TR 7050-5, May 1965.
• 6: John D. Burle, Fast Convolution with Finite Field Fast Transforms, -IEEE-ASSP, Vol. 23 #2, Apr., 1975, p. 240.
• 7: B.Liu, Effect of Finite Word Length on the Accuracy of Digital Filters-A Review, IEEE Trans. Circuit Theory, Vol. CT-18, pp.670-677, Nov., 1971.
• 8: S.Zohar, New Hardware Realizations of Non-recursive Digital Filters, IEEE Trans. on Comp., Vol. C-22, pp. 328-338, Apr., 1973.
• 9: P.W.Baker, More Efficient Radix-2 Algorithms for Some Elementary Functions, IEEE Trans. on Computers, Vol. E6-24, #11, pp. 1049-1054, Nov., 1975.
• 10: M.Andrews, A Hardwired Digital Resolver, Thesis, University of Arizona, Tucson, 1968.
• 11: S.F.McCormick, An Efficient Algorithm for Optimal Control of a Domestic Solar Energy Source Using a Microprocessor, in preparation.
• 12: W. J. Cody, Double-precision square root for the CDC-3600, Communications of the ACM, v.7 n.12, p.715-718, Dec. 1964 [doi>10.1145/355588.365122]
• 13: J.Eve, Starting approximations for the iterative calculation of square roots, Comput. J. 6(1963), 274-276.
• 14: C. T. Fike, Starting approximations for square root calculation on IBM system /360, Communications of the ACM, v.9 n.4, p.297-299, April 1966 [doi>10.1145/365278.365556]
• 15: David G. Moursund, Optimal starting values for Newton-Raphson calculation of x^{1 2} , Communications of the ACM, v.10 n.7, p.430-432, July 1967 [doi>10.1145/363427.363454]
• 16: Richard F. King , David L. Phillips, The logarithmic error and Newton's method for the square root, Communications of the ACM, v.12 n.2, p.87-88, Feb. 1969 [doi>10.1145/362848.362861]
• 17: I.Ninomlya, Best rational starting approximations and improved Newton iteration for square root, Math. Comp. 24(1970), 391-404.
• 18: P.H.Sterbenz and C.T.Fike, Optimal Starting approximations for Newton's method, Math. Comp. 23(1969), 313-318.
• 19: J.Taylor, Microcomputer Control of a Solar House, Thesis, Colorado State University, Fort Collins, 1974.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Microprocessors

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

General Terms:
Algorithms, Theory