Algorithm 650: Efficient square root implementation on the 68000

ABSTRACT

Two square root algorithms (for integer and floating point data types) are presented, which are simpler and more efficient than standard procedures. These could be effectively used as the basis of hardware-based square root generators as well as for software implementations. One possible appli- cation for an efficient square root routine would be in calculating trigonometric and exponential functions. (This application may be primarily of academic interest, however, since standard tran- scendental function generators would generally be more efficient.) Three accompanying MC68000 implementations of the algorithm for 32-bit integer and IEEE single- and double-precision data are available on the CALGO listing. These programs return rounding status in the condition code register, and they exhibit the following approximate runtime performance at 8 MHz: 105-134 ps (integer); 180-222 ps (single precision); 558-652 ps (double precision).

REFERENCES

• 1: JOHNSON, K. C. Listings for implementations of the algorithm for the MC68000. CALGO (1987).
• 2: STEVENSON, D. A proposed standard for binary floating point arithmetic. Computer 14, 3 (Mar. 1981), 51-62.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Algorithm design and analysis

General Terms:
Algorithms, Measurement, Performance

Keywords:
MC68000, square root