 Newton inversion of a formal power series

Suppose $f$ is a formal power series with invertible constant coefficient and $g$ satisfies $fg\equiv 1(\mathrm{mod}{x}^m)$. The updateis an inverse modulo $x^{2m}$, because $1-f{g}_{\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.