algorithm - O(log log n) 算法，用于确定 n 是否为完美平方

Question

是否有任何已发布的 O(log b) 算法来确定 b 位数是否是整数的平方？

（如果这个问题超出了本网站的范围，我深表歉意，如果是，我很乐意检索它）

更新：我意识到我提出的问题是不合理的。因此，让我通过询问 b 中的子多项式运算的任何算法来修改它。对于常数 k，不一定是 O(log^kb)，并且具有“合理”的空间复杂度。操作是在通常意义上定义的：对于手头的任务是合理的（例如，加法、求反、异或、与、或等）

后记：现在我意识到我的问题是无稽之谈。计算一个 n 位数的底平方根的成本小于将两个 n 位数相乘。

score 0 · Accepted Answer

如果b足够小，那么使用sqrttable 是复杂的O(1)
如果不是，那么使用位近似是复杂的O(b/2) = O(log n)
使用完美的方桌也很复杂O(b/2) = O(log n)

但是使用更快的操作（仅比较和位操作）b位数可以是最大b/2位数的完美平方，因此表具有位数的2^(b/2)条目b并且近似索引搜索（类似于二进制搜索）需要b/2步骤
可以通过近似来进行一些改进

现在创建近似函数y=approx_sqrt(x);并计算y，您可以检查< y-c , y+c > 具有运行时间的值，其中~T(2c)常数c取决于近似精度(1,2,3,...)。大多数近似值都关闭了较大的值，因此您可以制作c=log(b)并且您的复杂性突然O(log b) = O(log log n)变得如此，这就是您正在寻找的我认为。

[编辑]

在否决投票之后，我发现标记隐藏了我的部分文字

假设一些格式或其他什么，< interval >所以我添加了几个空格来取消隐藏它，还发现项目符号#5是错误的，所以我删除了它。如果这是拒绝投票的原因，而不是感谢它，我忽略了它……最近在用素数做一些事情……所以我的大脑在没有仔细考虑的情况下将其复制到那里

由于通常没有代码和 Wiki 页面，你们中的一些人不相信，只是投了反对票，所以这是我上面测试过的实现：

//---------------------------------------------------------------------------
int  is_square(int x,int &cnt)      // return sqrt(x) if perfect or 0, cnt = num of cycles ~ runtime
    {
    int y,yy;
    // y=aprox_sqrt(x)
    for (y=x,yy=x;yy;y>>=1,yy>>=2); // halves the bit count
    if (y) y=(y+(x/y))>>1;          // babylonian approximation
    if (y) y=(y+(x/y))>>1;
    if (y) y=(y+(x/y))>>1;
    // check estimated y and near values
    cnt=1;
    yy=y*y; if (yy==x) return y;
    if (yy<x) for (;;)
        {
        cnt++;
        y++;
        yy=y*y;
        if (yy==x) return y;
        if (yy> x) return 0;
        }
    else for (;;)
        {
        cnt++;
        y--;
        yy=y*y;
        if (yy==x) return y;
        if (yy< x) return 0;
        }
    }
//---------------------------------------------------------------------------

我为您添加了cnt，因此您可以自己测试复杂性。我使用的 approx 需要一个好的起始值，所以我使用将位数减半，这显然是O(log b)但对于bignums和float值，指数/位计数是已知的，因此它仅转换为单个位/字/基数/指数移位O(1)。顺便说一句，这是IEEE 浮点魔术sqrt，由orlog函数的大多数近似值完成。

我的测量结果比我最初的估计要好（即使是不精确的巴比伦近似值）：
```
/*----------------
|          N | T |
------------------
| 1000000000 | 6 |
|  100000000 | 4 |
|   10000000 | 2 |
|    1000000 | 2 |
----------------*/
```
测试它N的循环在哪里。是不同近似值的测试数字的最大值（更适合您的需要）可以看这里NTcnt< 0,N >

所以我对你的问题的回答是肯定O(log n)的，它确实存在一个比确定是否是完美平方更快的算法n（例如我的上面也计算sqrt）但是如果你还计算基本函数的复杂性，那么我担心答案是不，因为偶数位操作在bignumsO(log n)上！！！

顺便说一句，二进制搜索sqrt也可以在没有乘法的情况下完成。

希望能帮助到你。

algorithm - O(log log n) 算法，用于确定 n 是否为完美平方

1 回答 1

Related

Reference