java - 查找小于 n 的最大平方数的算法

Question

如何有效地找到小于给定 int n 的最大平方数(即 4、9、16)？我有以下尝试:

int square = (int)Math.sqrt(number);
return square*square;

但它的明显效率低下是为了得到一个平方根才可以对它进行平方。

Answer 1

预先说明:应该注意的是，能够将 sqrt 作为机器指令执行的处理器速度足够快。毫无疑问，它的(微)程序使用了 Newton-Raphson，并且该算法是二次收敛的，每次迭代都会将准确数字的数量加倍。

所以，像这样的想法并不值得追求，尽管它们使用了正方形等不错的属性。(请参阅下一个建议)

// compute the root of the biggests square that is a power of two < n
public static int pcomp( int n ){
  long p2 = 1;
  int i = 0;
  while( p2 < n ){
    p2 <<= 2;
    i += 2;
  }
  p2 >>= 2;
  i -= 2;
  return (int)(p2 >>= i/2);
}

public static int squareLowerThan( int n ){
  int p = pcomp(n);
  int p2 = p*p;     // biggest power of two that is a square < n 
  int d = 1;        // increase using odd numbers until n is exceeded
  while( p2 + 2*p + d < n ){
    p2 += 2*p + d;
    d += 2;
  }
  return p2;
}

但我确信牛顿算法更快。二次收敛，记住。

public static int sqrt( int n ){
  int x = n;
  while( true ){
    int y = (x + n/x)/2;
    if( y >= x ) return x;
    x = y;
  }
}

这将返回整数平方根。返回 x*x 得到 n 下面的方 block 。