java - 对于序列的每个成员，确定它是否是一个理想的正方形

我要问的不是this very popular question的重复项。对于随机选择的输入，可以进行一些快速测试，如果不能说“不是平方”，则必须对平方根进行一些计算（我自己也尝试过solution）。

当要测试的数字来自一个简单的序列时，情况就不同了，因为可以使用前一个（近似）平方根。对于琐碎的序列，它也是琐碎的，例如，

long sqrt = 1;
for (long i=1; i<limit; ++i) {
   if (sqrt*sqrt == i) {
       handleSquare(i);
       ++sqrt;
   }
}

我的问题是如何处理更复杂的序列，例如

x[i] = start + i*i;

要么

x[i] = start - i*i*i;

我正在考虑牛顿法，但是我看不到如何使其快速进行（因为除法是一项非常昂贵的操作）。

最佳答案

您想对算法应用哪种序列？以下是x [i]发散但不太快时应能很好地工作的解决方案。

例如，如果

x[i] = a*i^p + o(i^p)

而且我足够大，那么你将有

x[i+1]-x[i] ~ p * a * i^{p-1}.

如果y [i]表示最大整数，则

y[i]^2 <= x[i]

那你有

y[i] ~ sqrt(a) i^{p/2}

和

y[i+1]-y[i] ~ 1/(2 y[i]) * (x[i+1]-x[i]) ~ p/2 * sqrt(a) i^{p/2-1}

因此，您可以将其作为y [i + 1]的猜测，然后更新为正确的值，这样可以节省一些迭代。

通常，您始终可以使用公式

y[i+1]-y[i] ~ 1/(2 y[i]) * (x[i+1]-x[i])

作为猜测，但这仅在x [i + 1] -x [i]相对于y [i] ^ 2-即相对于x [i]较小时才有用。使用（精确的）二阶展开式可能还需要在公式上进行一些改进

y[i+1]^2 = y[i]^2 + 2y[i](y[i+1]-y[i]) + (y[i+1]-y[i])^2

为了提高对y [i + 1]的猜测。

请注意，如果在i较大时x [i]保持有界或x呈指数快变化，则此方法将无法正常工作。