Publications [#236976] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, Approximate complex polynomial evaluation in near constant work per point, SIAM Journal on Computing, vol. 28 no. 6 (January, 1999), pp. 2059-2089, Society for Industrial & Applied Mathematics (SIAM) [pdf], [doi]
   (last updated on 2026/01/16)

   Abstract:
   The n complex coefficients of a degree n-1 complex polynomial are given and this polynomial is evaluated at a large number m≥n of points on the complex plane. This problem is required by many algebraic computations and so is considered in most basic algorithm texts. An arithmetic model of computation is assumed. Approximation algorithms for complex polynomial evaluation that cost, in many cases, near constant amortized work per point are presented.