Newton's Method for Polynomial Exponentiation

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

Algorithm

Lemma

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

Proof

Let
$h (y) = lo g_{e} y - f (x)$
then
$h (e^{f (x)}) = 0 ⟺ k = 0 \sum \infty \frac{h ^{(k)} ( g _{m} ( x ))}{k !} (e^{f (x)} - g_{m} (x)) = 0 ⟹ h (g_{m} (x)) + h^{'} (g_{m} (x)) (e^{f (x)} - g_{m} (x)) \equiv 0 (mod x^{2 m}) ⟺ e^{f (x)} \equiv g_{m} (x) - \frac{h ( g _{m} ( x ))}{h ^{'} ( g _{m} ( x ))} (mod x^{2 m}) ⟺ e^{f (x)} \equiv g_{m} (x) - g_{m} (x) (lo g_{e} 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) = (lo g_{e} g_{m} (x) - f (x)) mod x^{2 m}$ . Apply Newton’s Method for Polynomial Logarithms to find $P (x)$ .
Let $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 1 to find $g_{m} (ω_{N}^{0}) - g_{m} (ω_{N}^{0}) P (ω_{N}^{0}), g_{m} (ω_{N}^{1}) - g_{m} (ω_{N}^{1}) P (ω_{N}^{1}), \dots, g_{m} (ω_{N}^{N - 1}) - g_{m} (ω_{N}^{N - 1}) P (ω_{N}^{N - 1})$ .
Apply the Inverse Fast Fourier Transform to find $g_{m} (x) - 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_exp(const std::vector<std::complex<double>> &a, int n) {
	std::vector x = {std::complex(1.)};
	for (int m = 1; m < n; m *= 2) {
		auto y = newton_log(x, 2 * m);
		for (int i = 0; i < std::min(2 * m, int(a.size())); i++) {
			y[i] -= a[i];
		}
 
		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] -= 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 Exponentiation

Algorithm

Graph View

Backlinks