我正在寻找确定长值是否为完美平方(即其平方根是另一个整数)的最快方法:

我使用内置的Math.sqrt()以简单的方式完成了这项工作函数,但我想知道是否有一种方法可以通过将自己限制为仅限整数的域。维护查找表是不切实际的(因为平方小于263的231.5个整数)。

下面是我现在做的非常简单明了的方法:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

注意:我在许多Project Euler问题中都使用了这个函数。因此,其他人将永远不必维护此代码。而这种微优化实际上可能会有所不同,因为挑战的一部分是在不到一分钟的时间内完成每一个算法,而在某些问题中,这个函数需要调用数百万次。


我尝试了不同的解决方案:

经过详尽的测试,我发现不需要在Math.sqrt()的结果上加0.5,至少在我的机器上是这样。快速平方根逆运算速度更快,但对于n>=410881,它给出了错误的结果。然而,正如BobbyShaftoe所建议的,我们可以在n<410881时使用FISR黑客。牛顿的方法比Math.sqrt()慢得多。这可能是因为Math.sqr()使用了类似于牛顿方法的东西,但在硬件中实现,所以比Java快得多。此外,牛顿法仍然需要使用双精度。一个经过修改的牛顿方法使用了一些技巧,因此只涉及整数数学,需要一些技巧来避免溢出(我希望这个函数可以处理所有64位有符号的正整数),而且它仍然比math.sqrt()慢。二元斩更慢。这是有意义的,因为二进制斩波平均需要16次才能找到64位数字的平方根。根据John的测试,在C++中使用or语句比使用switch更快,但在Java和C#中,or和switch之间似乎没有区别。我还尝试创建一个查找表(作为64个布尔值的私有静态数组)。然后,我只说if(lookup[(int)(n&0x3F)]){test}else return false;,而不是switch或or语句;。令我惊讶的是,这(只是稍微)慢了一些。这是因为在Java中检查数组边界。


当前回答

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

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);
    }
}

其他回答

如果你想要速度,考虑到整数的大小是有限的,我想最快的方法是(a)按大小划分参数(例如,按最大位集划分类别),然后对照该范围内的完美平方数组检查值。

使用牛顿的方法计算整数平方根,然后对这个数字进行平方并进行检查,这应该快得多,就像您在当前解决方案中所做的那样。牛顿方法是其他答案中提到的卡马克解的基础。你应该能够得到更快的答案,因为你只对根的整数部分感兴趣,这样你就可以更快地停止近似算法。

另一个可以尝试的优化:如果数字的数字根不以1、4、7或9这个数字不是一个完美的正方形。这可以作为在应用较慢的平方根算法之前消除60%输入的快速方法。

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

考虑到一般的比特长度(尽管我在这里使用了特定的类型),我试图设计如下的简单算法。最初需要对0,1,2或<0进行简单而明显的检查。以下是简单的,因为它不试图使用任何现有的数学函数。大多数运算符可以用逐位运算符替换。我还没有用任何基准数据进行测试。我既不是数学专家,也不是计算机算法设计专家,我很乐意看到你们指出这个问题。我知道那里有很多改进的机会。

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}  

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

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