Methods of evaluating polynomial approximations in function evaluation routines

ABSTRACT

The method of nested multiplication is commonly used in function evaluation routines to evaluate approximation polynomials. New polynomial evaluation methods have been developed in recent years which require fewer multiplications than nested multiplication and may therefore be preferable for use in function evaluation routines. Although some of these methods do not appear to be practically useful because of rounding-error difficulties, several methods of evaluating low-degree polynomials have been found to be satisfactory. Three such methods are described and illustrated.

REFERENCES

• 1: TODD, J. Motivation for working in numerical analysis. Comm. Pure Appl. Math. 8 (1951), 97-116.
• 2: MOTZHIN, T.S. Evaluation of polynomials. Bull. Am. Math. Soc. 61 (1955), 163.
• 3: BELAGA, E.G. Some problems involved in the calculation of polynomials. Dokl. Akad. Nauk SSSR 128 (1958), 775-777.
• 4: PAN, V. YA. Schemes for the computation of polynomials with real coefficients. Dokl. Akad. Nauk SSSR 127 (1959), 266-269.
• 5: Certain schemes for the calculation of values of polynomials with real coefficients. Probl. Kibernetiki 5 (1959), 17-29.
• 6: Donald E. Knuth, Evaluation of polynomials by computer, Communications of the ACM, v.5 n.12, p.595-599, Dec. 1962 [doi>10.1145/355580.369074]
• 7: EVE, J. The evaluation of polynomials. Numer. Math. 6 (1964), 17-21.
• 8: LYUSTERNIK, L. A., CHERVONENKIS, O. A., AND YANPOL'SKII, A. R. Handbook for Computing Elementary Functions. English tr. by G. J. Tee. Pergamon Press, New York, 1965.
• 9: RICE, J. On the conditioning of polynomial and rational forms. Numer. Math. 7 (1965), 426-435.
• 10: IBM System/360 operating system FORTRAN IV (E) library subprograms. Form C28-6596-0, IBM Corp., 1966.
• 11: IBM 7090/7094 IBSYS operating system, version 13, IBJOB processor. Form C28-6389-2, IBM Corp., 1965.
• 12: FORTRAN specifications and operating procedures, IBM 1401. Form C24-1455-2, IBM Corp., 1964.
• 13: IBM System/360 basic programming support, FORTRAN IV, 360P-FO-031, programmer's guide. Form C28-6583-0, IBM Corp., 1965.
• 14: OSTROWSKI, A. M. On two problems in abstract algebra connected with Horner's rule. In Studies in Mathematics and Mechanics Presented to R. yon Mists, Academic Press, New York, 1954, pp. 40-48.
• 15: S. H. Eisman, Polynomial evaluation revisited, Communications of the ACM, v.6 n.7, p.384-385, July 1963 [doi>10.1145/366663.366668]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory