Polynomial Inverse DSL

Initially, $g=f_0^{-1}$ satisfies $fg\equiv 1\pmod{x}$. Given an inverse of length $m$, the Newton update

$$g' = 2g-fg^2\pmod{x^{2m}}$$

doubles the precision. A direct implementation with two full convolutions is correct, but its normalized cost is about $24$ for $N=2^{20}$, so it does not receive full score.

The full-score construction recovers the required high half of $q=fg^2$ from two cyclic views. Treat $g$ as a length-$m$ polynomial and truncate $f$ to length $2m$.

First compute

$$u=q\bmod (x^{2m}-1)$$

with a cyclic convolution of length $2m$. This uses two length-$2m$ DFTs and one IDFT.

Next, let $r$ be a primitive $4m$-th root and let $j=r^m$. Multiply coefficient $i$ by $r^i$, fold $f$ modulo $x^m-1$, and perform a cyclic convolution of length $m$. After the inverse transform, multiply coefficient $i$ by $r^{-i}$. The result is

$$v_k=q_k+jq_{k+m}-q_{k+2m}-jq_{k+3m}.$$

For $0\le k<m$, write

$$A=q_k,\quad B=q_{k+m},\quad C=q_{k+2m},\quad D=q_{k+3m}.$$

Then

$$u_{\mathrm{low}}=A+C,\qquad u_{\mathrm{high}}=B+D,$$ $$v=A+jB-C-jD.$$

Because $fg\equiv 1\pmod{x^m}$, we have $q=fg^2\equiv g\pmod{x^m}$, so $A=g_k$. Therefore,

$$-B=\frac{j(u_{\mathrm{low}}+v-2g)-u_{\mathrm{high}}}{2}.$$

The new high half in the Newton update is exactly $-B$, so compute this expression and append it to $g$.

Each doubling step uses three transforms of length $2m$ and three transforms of length $m$. For $N=2^K$, the total cost is

$$3\sum_{k=0}^{K-1}\left(D(2^{k+1})+D(2^k)\right) =(9K-12)N+12.$$

Thus, for $N=2^{20}$,

$$C=8.400000572\ldots<9,$$

which receives full score. When $N$ is not a power of two, zero-pad at each step and truncate to length $N$ at the end.

The frequency order of DFT output is irrelevant. The construction only multiplies DFT outputs produced at the same length, so the opaque-order guarantees in the specification are sufficient.

Solution written by GPT5.6