Approximate complex polynomial evaluation in near constant work per point
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.