Yes will update

Oops. Indeed! Fixed.

Computing $\prod _{j\neq i}(x-x_j),\forall i$ can be done in $O(n)$ time (for a fixed $x$). Computing $g'(x_i),\forall i$ takes $O(n^2)$ time, unfortunately. Even if that could be done faster (which is what I'm trying to do via FFT multipoint evaluation), computing $f(x_i),\forall i$ would still take $O(n^2)$ time (or can be sped up using FFT multipoint evaluation, which reduces to computing remainders fast).

Oh, I see. It's basically the Lagrange formula applied to $f(x) \bmod \prod (x-x_i)$. Never saw it stated in this way before. Thank you! Unfortunately, not sure how I can make use of it. The reason I'm asking about computing remainders fast is precisely because I want to speed up Lagrange interpolation itself. Computing your formula naively would take $O(n^2)$ time when $\deg{g} = n$. Computing it asymptotically faster reduces to computing remainders fast!

Thank you! Can you please clarify the $(\partial _i g)(x_i)$ notation? I'm assuming $g'(x_i)$ is the formal derivative of $g$ evaluated at $x_i$, but what is $(\partial _i g)(x_i)$? Is $\partial_i$ the $i$th Lagrange coefficient? Are you composing it with $g$?

Thank you! I messed up but updated the post: The $x_i$'s can be an $\ell$th root of unity for some $\ell > k$ but they won't always be the $i$th $\ell$th root of unity. In other words, it's possible to have $x_1 = \omega^2, x_2 = \omega^5, x_3 = \omega^7, \dots$.