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

Question

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

3

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

（如果这个问题超出了本网站的范围，我很抱歉，并会在需要时撤回它）

更新：我意识到我的问题所提出来是不合理的。让我修改一下，询问任何次多项式操作算法，其复杂度为b。不一定是O(log^k b)（k为常数），并且具有“合理”的空间复杂度。操作是以通常的方式定义的：对于手头的任务合理的操作（例如添加，否定，异或，and, or等）。

附言：现在我意识到我的问题是无意义的。计算n位数字的floor square root的成本小于乘两个n位数字。

- user2943324

3

cstheory.stackexchange.com可能会给您提供更好的答案。 - Millie Smith

您也可以从以下页面中受益： http://math.stackexchange.com/questions/41337/efficient-way-to-determine-if-a-number-is-perfect-square - bdean20

1

@BrianDHall 你不能寻找计算sqrt的最快方法并希望复杂度更低。通常相反，因为优化的代码不是降低复杂度，而是使用快速操作，例如如果你使用一个超级逼近多项式，那么复杂度是O(1)，但是O(log N)的方法可能会快1000倍（通常甚至更快）。 - Spektre

1

还有一个有用的链接：http://math.stackexchange.com/q/131330，它似乎是你在cstheory上发布的问题的副本。 - Jim Mischel

1

我所理解的是：这是不可能的。读取一个 b 位数需要 O(b) 的工作量。而且你需要读取所有的 b 位才能确认这个数字是完全平方数。（虽然有时可以在不查看所有位的情况下证明某个 b 位数不是完全平方数。） - Mysticial

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Spektre · Answer 1

如果 b 足够小，那么使用 sqrt 表的复杂度为 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)，这正是您正在寻找的东西。

以下是我测试过的实现：

    //---------------------------------------------------------------------------
    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)，但对于和float值，指数/位数已知，因此只需转换为单个位/字/基数/指数移位O(1)。顺便说一句，这就是大多数sqrt或log函数的近似所做的IEEE浮点魔术。

我的测量结果比我最初的估计更好（即使是非精确的巴比伦近似）：

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

其中N是循环N，用于测试。 T是在不同的近似值（更适合您的需求）下测试数字< 0，N>的最大cnt值，可以在这里查看。

所以我的答案是是的，存在比O(log n)更快的算法来确定n是否为完全平方数（例如上面的算法也计算了sqrt），但如果您还要计算基本函数的复杂度，那么恐怕答案是否，因为即使是位运算在大数上也是O(log n)！

顺便说一句，二分查找sqrt也可以不使用乘法。