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

我使用内置的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中检查数组边界。


当前回答

标签中提到了项目Euler,其中的许多问题需要检查数字>>2^64。当您使用80字节缓冲区时,上面提到的大多数优化都不容易工作。

我使用了javaBigInteger和稍微修改过的Newton方法,它对整数更有效。问题是,精确的平方n^2收敛到(n-1)而不是n,因为n^2-1=(n-1)(n+1),最终误差仅比最终除数低一步,算法终止。在计算错误之前,通过在原始参数中添加一个参数很容易解决。(为立方体根等添加两个)

这个算法的一个优点是,你可以立即判断出这个数字是否是一个完美的平方-牛顿方法中的最终误差(不是校正)将为零。一个简单的修改也可以让您快速计算floor(sqrt(x)),而不是最接近的整数。这对于几个Euler问题很方便。

其他回答

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

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

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

这里有一个分而治之的解决方案。

如果自然数(数字)的平方根是自然数(解),您可以根据数字的位数轻松确定解的范围:

数字有1位:范围内的解=1-4数字有2位数:范围内的解=3-10数字有3位数:范围内的解=10-40数字有4位数字:范围=30-100数字有5位数:范围内的解=100-400

注意到重复了吗?

您可以在二进制搜索方法中使用此范围,以查看是否存在以下解决方案:

number == solution * solution

这是密码

这是我的类SquareRootChecker

public class SquareRootChecker {

    private long number;
    private long initialLow;
    private long initialHigh;

    public SquareRootChecker(long number) {
        this.number = number;

        initialLow = 1;
        initialHigh = 4;
        if (Long.toString(number).length() % 2 == 0) {
            initialLow = 3;
            initialHigh = 10;
        }
        for (long i = 0; i < Long.toString(number).length() / 2; i++) {
            initialLow *= 10;
            initialHigh *= 10;
        }
        if (Long.toString(number).length() % 2 == 0) {
            initialLow /= 10;
            initialHigh /=10;
        }
    }

    public boolean checkSquareRoot() {
        return findSquareRoot(initialLow, initialHigh, number);
    }

    private boolean findSquareRoot(long low, long high, long number) {
        long check = low + (high - low) / 2;
        if (high >= low) {
            if (number == check * check) {
                return true;
            }
            else if (number < check * check) {
                high = check - 1;
                return findSquareRoot(low, high, number);
            }
            else  {
                low = check + 1;
                return findSquareRoot(low, high, number);
            }
        }
        return false;
    }

}

下面是一个如何使用它的示例。

long number =  1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
static boolean isPerfectSquare (int input) {
  return Math.sqrt(input) == (int) Math.sqrt(input);
}

如果输入的平方根的整数值等于双倍值,则返回该值。这意味着它是一个整数,它将返回true。否则,将返回false。

考虑到一般的比特长度(尽管我在这里使用了特定的类型),我试图设计如下的简单算法。最初需要对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;  
}  

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;

会影响性能。