牛顿迭代法

[Xeonacid]

https://oi-wiki.org/math/newton-method/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[yanjinbin]

也叫牛顿求根法

[Vladimir-Chenyuan-Ostrovsky]

这在高中课本里叫做牛顿法——用导数逼近方程根

[BeautyyuYanli]

更完整的称呼应为Newton-Raphson（牛顿拉弗森？） Method

[Minion123456]

我手写了一个 C++ 版本的高精度开根号，跑 $n=10^{1000000}-1$ 需要 48-49s，跑 $n=10^{1000000}$ 需要 0.8s 左右

[weilycoder]

我尝试了 $\sqrt[64]{2^{64}-1}$，按照文中提到的技巧 $x_0=1$，这是很接近的解，但无法立即返回（因为算法无法确定这一点），而 $x_1=288230376151711744$，这让时间无法承受（更难以接受的是，下一次迭代的中间结果将爆 __int128）。

使用 $x_0=2^{\frac{1}{2}\lfloor\log_2 n\rfloor+1}$ 会好一些，此时 $x_0=2,x_1=1$，按照算法逻辑，下一次迭代将可以返回比较精确的答案。

inline int qlog2(long long n) { return 63 - __builtin_clzll(n); }

__int128 root(__int128 n, int k) {
	if (!n) return 0;
	if (n == 1) return 1;
	if (k == 1) return n;
	if (k == 2) return isqrt_newton(n);
	__int128 x = ((__int128)2ll << (qlog2(n) / k));
	bool d = false;
	for (;;) {
		__int128 nx = ((k - 1) * x + n / qpow(x, k - 1)) / k;
		clog << nx << endl;
		if (x == nx || (nx > x && d)) break;
		d = nx < x, x = nx;
	}
	return x;
}

这段代码在 $n\lt 2^{64},k\le 64$ 时表现良好。但我没有对高精度测试。