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

复杂性为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;
}

有人指出，完美正方形的最后d位只能取某些值。数字n的最后d位（以b为基数）与n除以bd时的余数相同，即C符号n%pow（b，d）。

这可以推广到任何模数m，即n%m可以用来排除某些百分比的数字是完全平方。您当前使用的模数是64，这允许12，即19%的余数作为可能的平方。通过一点编码，我找到了模数110880，它只允许2016，即1.8%的余数作为可能的平方。因此，根据模数运算（即除法）和查找表与机器上的平方根的成本，使用这个模数可能会更快。

顺便说一句，如果Java有办法为查找表存储一个压缩的位数组，那么不要使用它。现在110880个32位字的RAM不多，提取一个机器字将比提取一个位更快。

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

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

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

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

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

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

maartinus解决方案的以下简化似乎使运行时减少了几个百分点，但我在基准测试方面做得不够好，无法产生我可以信任的基准：

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

值得检查的是，如何省略第一次测试，

if (goodMask << x >= 0) return false;

会影响性能。