| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Note on fast division algorithm for polynomials using Newton iteration | Zhengjun Cao
; Hanyue Cao
; | Date: |
17 Dec 2011 | Abstract: | 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
ceil}, x^{lceil
l/2^{r-1}
ceil},..., x^{lceil l/2
ceil}, 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. | Source: | arXiv, 1112.4014 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |