1

我要问的不是这个非常流行的问题的重复。对于随机选择的输入，可以进行一些快速测试，如果他们没有说“不是平方”，则必须进行平方根的一些计算（我自己也尝试了一个解决方案）。

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

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;

我正在考虑牛顿的方法，但我不知道如何让它快速（因为除法是一项非常昂贵的操作）。

4

1 回答 1

0

您想将您的算法应用于什么样的序列？下面是一个解决方案，当 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 以指数速度快速发散，则此方法将无法正常工作。

于 2015-04-27T09:13:21.370 回答