Newton's Method for Polynomial Logarithms

Newton’s Method for Polynomial Logarithms is an algorithm that computes ${\log }_{e}f(x)\mathrm{mod}{x}^n$ for a formal power series $f(x)$ such that $f(0)=1$ in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space.

Algorithm

Lemma

$${\log }_{e}f(x)=\int \frac{f^{\prime }(x)}{f(x)}\mathrm{d}x$$

Proof

$$\begin{array}{rl}{\log }_{e}f(x)& =\int \mathrm{d}({\log }_{e}f(x))\\ & =\int \frac{f^{\prime }(x)}{f(x)}\mathrm{d}x\end{array}$$

0. Let $P(x)=f^{\prime }(x)\mathrm{mod}{x}^{n-1},Q(x)=f(x{)}^{-1}\mathrm{mod}{x}^{n-1}$. Apply Newton’s Method for Polynomial Inversion to find $Q(x)$.
1. Let $N=2^{\lceil {\log }_2(2n-3)\rceil }$. Apply the Fast Fourier Transform to find $P({\omega }_N^0),P({\omega }_N^1),\dots ,P({\omega }_N^{N-1})$ and $Q({\omega }_N^0),Q({\omega }_N^1),\dots ,Q({\omega }_N^{N-1})$.
2. Use the results from 1 to find $P({\omega }_N^0)Q({\omega }_N^0),P({\omega }_N^1)Q({\omega }_N^1),\dots ,P({\omega }_N^{N-1})Q({\omega }_N^{N-1})$.
3. Apply the Inverse Fast Fourier Transform to find $P(x)Q(x)$.
4. Apply the lemma to find ${\log }_{e}f(x)\mathrm{mod}{x}^n$.

This algorithm solves the problem in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(n)$ space.

std::vector<std::complex<double>> newton_log(const std::vector<std::complex<double>> &a, int n) {
	if (n == 1) {
		return {0};
	}
 
	std::vector x(n - 1, std::complex(0.));
	for (int i = 1; i < std::min(n, int(a.size())); i++) {
		x[i - 1] = 1. * i * a[i];
	}
 
	auto y = newton_inv(a, n - 1);
 
	int m = std::bit_ceil<u32>(2 * n - 3);
	x.resize(m, 0), y.resize(m, 0);
	fft(m, x), fft(m, y);
	for (int i = 0; i < m; i++) {
		x[i] *= y[i];
	}
	ifft(m, x);
	x.resize(n - 1);
 
	x.insert(x.begin(), 0);
	for (int i = 1; i < n; i++) {
		x[i] /= i;
	}
	return x;
}