对于序列的每个成员，确定它是否是完美的正方形

提问于 2024-05-14T17:53:32+08:00

浏览次

1

我要问的不是this very popular question的副本 . 对于随机选择的输入，可以进行一些快速测试，如果他们不能说"not a square"，则必须进行平方根的一些计算（我自己也试过了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;

我正在考虑牛顿的方法，但我看不出如何使它快速（因为除法是一个非常昂贵的操作） .

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以指数方式快速偏离时x [i]仍然有界，这将无法正常工作 .
回复于 2024-05-14T17:53:32+08:00

相关问题