用于确定 n 是否完全平方的 O(log log n) 算法

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

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

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

后脚本: 现在我发现我的问题是无稽之谈。计算 n 位数字的下限平方根的成本小于两个 n 位数字相乘的成本。

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

但操作速度更快（只需比较和位操作）b位数可以是 max 的完全平方b/2位号，所以表中有2^(b/2)的条目b位数和近似索引搜索（类似于二分搜索）需要b/2 steps

4. 可以通过近似进行一些改进

创建近似函数y=approx_sqrt(x);并计算y现在你可以检查值< y-c , y+c > 有运行时间~T(2c) where c是常数，取决于近似精度(1,2,3,...)。大多数近似值都较大，因此您可以c=log(b)和你的复杂性突然出现O(log b) = O(log log n)我想这就是你正在寻找的东西。

这是我上面经过测试的实现：

    //---------------------------------------------------------------------------
    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，以便您可以自己测试复杂性。我使用的大约需要一个好的起始值，所以我将位数减半，这显然是O(log b)但对于bignums and float指数/位数已知，因此它仅转换为单个位/字/基数/指数移位O(1)。顺便说一句，这是IEEE 浮动魔法通过大多数近似来完成sqrt or log功能。

3. 我的测量结果比我的第一次估计要好（即使对于不精确的巴比伦近似）：

    /*----------------
    |          N | T |
    ------------------
    | 1000000000 | 6 |
    |  100000000 | 4 |
    |   10000000 | 2 |
    |    1000000 | 2 |
    ----------------*/
   

where N是循环N对其进行了测试。T is max cnt测试数字的值< 0,N >对于不同的近似值（更适合您的需求）可以看看here http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

所以我对你问题的回答是YES它确实存在一种比O(log n)用于确定是否n是完全平方（例如我上面的也计算sqrt）但如果​​你还计算基本函数的复杂性，恐怕答案是NO因为即使是位操作也是O(log n)在大数上！！！

BTW the 二分查找sqrt无需乘法也可以完成 https://stackoverflow.com/a/34657972/2521214.