= Newton inversion of a formal power series
{c}
= Newton iteration for power series inversion
{c}
{synonym}
= Newton series inversion
{c}
{synonym}
Suppose $f$ is a <formal power series> with invertible constant coefficient and $g$ satisfies $fg\equiv1\pmod{x^m}$. The update
$$
g_{\mathrm{new}}=g(2-fg)\pmod{x^{2m}}
$$
is an inverse modulo $x^{2m}$, because $1-fg_{\mathrm{new}}=(1-fg)^2$ before truncation. Each update doubles the number of correct coefficients.
Start with the inverse of the constant coefficient and repeat, truncating all products to the required order. For $f=1-x$, the first approximations are $1$, $1+x$, and $1+x+x^2+x^3$. With a <polynomial multiplication> cost $M(n)$ satisfying the usual growth assumptions, computing the first $n$ coefficients takes $O(M(n))$ operations. The identity is algebraic and remains valid in <characteristic> two.
Back to article page
