Publications [#237126] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, Approximate complex polynomial evaluation in near constant work per point, Conference Proceedings of the Annual ACM Symposium on Theory of Computing (January, 1997), pp. 30-39 [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   The polynomial at a large number of m≥n of points on the complex plane given the n complex coefficients of a degree n - 1 complex polynomial is evaluated. This problem is required by many algebraic computations and is considered in most basic algorithm texts. An arithmetic model for computation is assumed, where an arithmetic operation can be executed on each step, and is computed exactly. An approximation algorithm is provided for complex polynomial evaluation that cost near constant amortized work per point.