一个数字的平方根，假设该数字是一个完全平方。

复杂性为log（n）

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

如果速度是一个问题，为什么不将最常用的一组输入及其值划分到一个查找表中，然后执行您针对特殊情况提出的任何优化魔术算法？

不知道最快，但最简单的方法是以正常方式取平方根，将结果乘以自身，看看它是否与原始值匹配。

由于我们在这里讨论的是整数，fasted可能涉及一个集合，您可以在其中进行查找。

我不确定它是否会更快，甚至更准确，但你可以使用约翰·卡马克的神奇平方根算法来更快地解平方根。您可能很容易对所有可能的32位整数进行测试，并验证您实际上得到了正确的结果，因为这只是一个近似值。然而，现在我想起来，使用双打也是近似的，所以我不确定这会如何发挥作用。

如果最后的X位数字是N，那么应该可以更有效地包装“不能是完美的正方形”！我将使用java 32位int，并生成足够的数据来检查数字的最后16位，即2048个十六进制int值。

...

好吧。要么我遇到了一些超出我理解范围的数论，要么我的代码中有一个错误。无论如何，以下是代码：

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if(foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if(i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

结果如下：

（ed：由于pretify.js性能不佳而取消；查看修订历史以查看。）

整数问题需要整数解。因此

对（非负）整数进行二进制搜索，以找到最大的整数t，使t**2<=n。然后测试r**2=n是否精确。这需要时间O（log n）。

如果你不知道如何对正整数进行二进制搜索，因为集合是无界的，这很容易。首先计算二次幂的递增函数f（高于f（t）=t**2-n）。当你看到它变为正值时，你已经找到了一个上限。然后可以进行标准的二进制搜索。