Note on fast division algorithm for polynomials using Newton iteration

Details Note on fast division algorithm for polynomials using Newton iteration Note on fast division algorithm for polynomials using Newton iteration

2011-12-17

arxiv.org/abs/1112.4014v1

Computer Science

Symbolic Computation

5 pages

Scientific paper

The classical division algorithm for polynomials requires $O(n^2)$ 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, $x^l$, 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/2^r\rceil}, x^{\lceil l/2^{r-1}\rceil},..., x^{\lceil l/2\rceil}, x^l$, 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}\,x^{l}$ without any additional cost, when $l$ is not a power of 2.

Affiliated with

Also associated with

No associations

Rating

Note on fast division algorithm for polynomials using Newton iteration does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on fast division algorithm for polynomials using Newton iteration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on fast division algorithm for polynomials using Newton iteration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-171249