Skip to content

Commit 9c7b6a6

Browse files
authored
Update polynomial.md
1 parent 7492537 commit 9c7b6a6

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/algebra/polynomial.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -192,7 +192,7 @@ This algorithm was mentioned in [Schönhage's article](http://algo.inria.fr/semi
192192

193193
$$A^{-1}(x) \equiv \frac{1}{A(x)} \equiv \frac{A(-x)}{A(x)A(-x)} \equiv \frac{A(-x)}{T(x^2)} \pmod{x^k}$$
194194

195-
Note that $T(x)$ can be computed with a single multiplication, after which we're only interested in the first half of coefficients of its inverse series. This effectively reduces the initial problem of computing $A^{-1} \pmod{x^k}$ to computing $T^{-1} \pmod{x^{\lfloor k / 2 \rfloor}}$.
195+
Note that $T(x)$ can be computed with a single multiplication, after which we're only interested in the first half of coefficients of its inverse series. This effectively reduces the initial problem of computing $A^{-1} \pmod{x^k}$ to computing $T^{-1} \pmod{x^{\lceil k / 2 \rceil}}$.
196196

197197
The complexity of this method can be estimated as
198198

0 commit comments

Comments
 (0)