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

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


当前回答

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

其他回答

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

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

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

sqrt调用并不完全准确,正如前面所提到的,但它很有趣,也很有启发性,因为它不会在速度方面影响其他答案。毕竟,sqrt的汇编语言指令序列很小。英特尔有一个硬件指令,我相信Java不会使用它,因为它不符合IEEE。

那么为什么速度慢呢?因为Java实际上是通过JNI调用一个C例程,而且这样做实际上比调用一个Java子程序慢,而Java子程序本身比内联调用慢。这很烦人,Java本应该想出更好的解决方案,即在必要时构建浮点库调用。哦,好吧。

在C++中,我怀疑所有复杂的替代方案都会失去速度,但我还没有检查过它们。我所做的,也是Java人会发现有用的,是一个简单的黑客,是a.Rex建议的特例测试的扩展。使用单个长值作为位数组,不检查边界。这样,您就有了64位布尔查找。

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

在我的core2双人游戏机上,PerfectSquare5的程序运行时间约为1/3。我怀疑,沿着相同的路线进一步调整可能会进一步缩短平均时间,但每次检查时,你都在用更多的测试来换取更多的消除,所以你不能在这条路上走得太远。

当然,你可以用同样的方法检查高6位,而不是单独测试阴性。

请注意,我所做的只是消除可能的正方形,但当我有一个潜在的情况时,我必须调用原始的内联的isPerfectSquare。

init2例程被调用一次以初始化pp1和pp2的静态值。请注意,在我的C++实现中,我使用的是无符号long-long,因此,既然有符号,就必须使用>>>运算符。

没有内在的必要对数组进行边界检查,但Java的优化器必须很快地解决这一问题,所以我不怪他们。

我希望此功能与所有正64位有符号整数

Math.sqrt()使用double作为输入参数,因此对于大于2^53的整数,不会得到准确的结果。

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

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

数字有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"

这是旧的Marchant计算器算法(抱歉,我没有参考)从十进制到二进制的修改,在Ruby中,专门针对这个问题进行了修改:

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

这里有一个类似的处理方法(可能有编码风格/气味或笨拙的O/O——重要的是算法,C++不是我的母语)。在这种情况下,我们要查找残数==0:

#include <iostream>  

using namespace std;  
typedef unsigned long long int llint;

class ISqrt {           // Integer Square Root
    llint value;        // Integer whose square root is required
    llint root;         // Result: floor(sqrt(value))
    llint residue;      // Result: value-root*root
    llint onebit, x;    // Working bit, working value

public:

    ISqrt(llint v = 2) {    // Constructor
        Root(v);            // Take the root 
    };

    llint Root(llint r) {   // Resets and calculates new square root
        value = r;          // Store input
        residue = value;    // Initialise for subtracting down
        root = 0;           // Clear root accumulator
        
        onebit = 1;                 // Calculate start value of counter
        onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
        while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value
        
        while (onebit > 0) {
            x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
            if (residue >= x) {         // Room to subtract?
                residue -= x;           // Yes - deduct from residue
                root = x + onebit;      // and step root
            };
            root >>= 1;
            onebit >>= 2;
        };
        return root;                    
    };
    llint Residue() {           // Returns residue from last calculation
        return residue;                 
    };
};

int main() {
    llint big, i, q, r, v, delta;
    big = 0; big = (big-1);         // Kludge for "big number"
    ISqrt b;                            // Make q sqrt generator
    for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
        q = b.Root(i);                  // Get the square root
        r = b.Residue();                // Get the residue
        v = q*q+r;                      // Recalc original value
        delta = v-i;                    // And diff, hopefully 0
        cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
    };
    return 0;
};