2011/12/17 by Zhengjun Cao, Cao, Zhengjun, Hanyue Cao +1
Computer Science · Mathematics · #Digital Filter Design and Implementation #FOS: Computer and information sciences #Iterative Methods for Nonlinear Equations #Numerical Methods and Algorithms #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.1112.4014
5 pages
arxiv created 2011/12/17 · openalex publication_date 2011/12/17 · arxiv updated 2011/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The classical division algorithm for polynomials requires O(n2) operations for inputs of size n. Using reversal technique and Newton iteration, it can be improved to O(M(n)), where M is a multiplication time. But the method requires that the degree of the modulo, xl, should be the power of 2. If l is not a power of 2 and f(0)=1, Gathen and Gerhard suggest to compute the inverse,f-1, modulo x\lceil l/2r\rceil, x^\lceil l/2r-1\rceil,..., x\lceil l/2\rceil, xl, separately. But they did not specify the iterative step. In this note, we show that the original Newton iteration formula can be directly used to compute f-1 mod xl without any additional cost, when l is not a power of 2.