Polynomial division with a remainder by means of evaluation and interpolation (Q1205721)

The authors apply the evaluation-interpolation technique of \textit{A. L. Toom} [The complexity of a scheme of functional elements realizing the multiplication of integers. Dokl. Akad. Nauk SSSR 150, 496-498 (1963)] to approximate polynomial division with a remainder. It is shown that the computational cost of the algorithm is bounded by \(O(\log m,m)\) [time, processors], where \(m\) is the degree of the divided polynomial. It is also shown that the computational errors are negligible provided that a sufficiently high floating point processor is used.