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

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

我喜欢对一些输入使用几乎正确的方法。这是一个“偏移”更高的版本。代码似乎有效，并通过了我的简单测试用例。

只需替换您的：

if(n < 410881L){...}

使用此代码：

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

用牛顿法计算平方根的速度快得惊人。。。只要起始值是合理的。然而，没有合理的起始值，在实践中，我们以平分和对数（2^64）行为结束。要真正做到快速，我们需要一种快速的方法来获得一个合理的初始值，这意味着我们需要进入机器语言。如果一个处理器在奔腾中提供了一个像POPCNT这样的指令，它对前导零进行计数，我们可以使用它来获得一个具有一半有效位的起始值。小心地，我们可以找到一个固定数量的牛顿步数，这将总是足够的。（因此，前面提到了需要循环并具有非常快的执行。）

第二种解决方案是通过浮点设备，它可能具有快速的sqrt计算（如i87协处理器）。即使通过exp（）和log（）进行偏移，也可能比牛顿退化为二进制搜索更快。这有一个棘手的方面，即依赖于处理器的分析，以确定后续是否需要改进。

第三种解决方案解决了一个稍有不同的问题，但很值得一提，因为问题中描述了情况。如果你想为稍有不同的数字计算很多平方根，你可以使用牛顿迭代，如果你从来没有重新初始化起始值，但只需将其保留在之前的计算停止的地方。我已经在至少一个欧拉问题中成功地使用了这一方法。

不确定这是否是最快的方法，但这是我（很久以前在高中）在数学课上无聊地玩计算器时偶然发现的。当时，我真的很惊讶这是有效的。。。

public static boolean isIntRoot(int number) {
    return isIntRootHelper(number, 1);
}

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}

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

复杂性为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可能涉及一个集合，您可以在其中进行查找。