Newton's Method for Polynomial Inversion

Newton’s Method for Polynomial Inversion is an algorithm that computes $f (x)^{- 1} mod x^{n}$ for a formal power series $f (x)$ such that $f (0) \neq = 0$ in $O (n lo g n)$ time and $O (n)$ space.

Tip

This problem can also be solved by Newton’s Method for Polynomial Powers in $O (n lo g n)$ time and $O (n)$ space.

Algorithm

Lemma

Let $g_{m} (x) = f (x)^{- 1} mod x^{m}$ , then
$\forall m \in Z_{+}, g_{2 m} (x) = g_{m} (x) (2 - g_{m} (x) f (x)) mod x^{2 m}$

Proof

Let
$h (y) = y^{- 1} - f (x)$
then
$h (f (x)^{- 1}) = 0 ⟺ k = 0 \sum \infty \frac{h ^{(k)} ( g _{m} ( x ))}{k !} (f (x)^{- 1} - g_{m} (x))^{k} = 0 ⟹ h (g_{m} (x)) + h^{'} (g_{m} (x)) (f (x)^{- 1} - g_{m} (x)) \equiv 0 (mod x^{2 m}) ⟺ f (x)^{- 1} \equiv g_{m} (x) - \frac{h ( g _{m} ( x ))}{h ^{'} ( g _{m} ( x ))} (mod x^{2 m}) ⟺ f (x)^{- 1} \equiv g_{m} (x) (2 - g_{m} (x) f (x)) (mod x^{2 m})$

For $m = 2^{0}, 2^{1}, \dots, 2^{⌈ l o g_{2} n ⌉ - 1}$ , find $g_{2 m} (x)$ in the following way:

Let $P (x) = f (x) mod x^{2 m}, N = 4 m$ . Apply the Fast Fourier Transform to find $g_{m} (ω_{N}^{0}), g_{m} (ω_{N}^{1}), \dots, g_{m} (ω_{N}^{N - 1})$ and $P (ω_{N}^{0}), P (ω_{N}^{1}), \dots, P (ω_{N}^{N - 1})$ .
Use the results from 0 to find $g_{m} (ω_{N}^{0}) (2 - g_{m} (ω_{N}^{0}) P (ω_{N}^{0})), g_{m} (ω_{N}^{1}) (2 - g_{m} (ω_{N}^{1}) P (ω_{N}^{1})), \dots, g_{m} (ω_{N}^{N - 1}) (2 - g_{m} (ω_{N}^{N - 1}) P (ω_{N}^{N - 1}))$ .
Apply the Inverse Fast Fourier Transform to find $g_{m} (x) (2 - g_{m} (x) P (x))$ .
Apply the lemma to find $g_{2 m} (x)$ .

This algorithm solves the problem in $O (n lo g n)$ time and $O (n)$ space.

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

Proof

$O k = 1 \sum ⌈ l o g_{2} n ⌉ k 2^{k} \subseteq O (lo g n) k = 1 \sum ⌈ l o g_{2} n ⌉ 2^{k} = O (n lo g n)$

Dong Xing's Blog

Explorer

Newton's Method for Polynomial Inversion

Algorithm

Graph View

Backlinks