寻找比n小的最大平方数的算法

Question

寻找比n小的最大平方数的算法

5

我该如何高效地找到一个给定的整数 n 之前的最大平方数（即4、9、16等）？我尝试了以下方法：

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

但这种方法存在明显的低效性，因为我们需要获取一个平方根然后再将其平方。

- David says Reinstate Monica

1

可能会有所帮助：http://en.wikipedia.org/wiki/Square_number - user180100

1

获取sqrt（n）的整数部分的最快方法 - hatchet - done with SOverflow

1

需要将 s/小于 n/不大于 n/g 来使您的代码正确。 - David Eisenstat

1

@Deduplicator 这看起来有些不可靠，但是 int->double 的转换是精确的，而 Math.sqrt 被保证正确舍入，因此我们可以进行误差分析来证明我们从不正确地将舍入向上到整数（这是截断可能出错的唯一方式）。 - David Eisenstat

什么是上下文？如果您正在尝试为循环找到限制，那么最好测试i * i < n作为您的循环终止条件，而不是i < precalculated_square_root。否则，在现代硬件上，浮点平方根可能是您能获得的最快速度。 - rici

显示剩余5条评论

3个回答

2

一种线性时间复杂度算法：

int largestSquare(int n) {
  int i = 0;
  while ((i+1)*(i+1) < n) {
    ++i;
  }
  return i*i;
}

- Andy Turner

3

如果这比求平方根更快，我会非常惊讶。 - David says Reinstate Monica

我也是。但你说你不想使用平方根。不使用平方根感觉像是微小的优化。 - Andy Turner

这绝对是微观优化。这就是我所要求的。但这根本不是一种优化。 - David says Reinstate Monica

你想要优化什么？例如，结果的查找表在时间上非常高效，但对于存储来说很糟糕。 - Andy Turner

2

有一种牛顿算法可以找到平方根，你需要的是m的平方而不是m，在给定的链接中。

https://math.stackexchange.com/questions/34235/algorithm-for-computing-square-root-of-a-perfect-square-integer

即使你想直接找到平方而不是找到m，我认为这样做也不会比这个更快。

这里有可用的工作代码。

public static int squareLessThanN(int N)
{
        int x=N;
        int y=(x+N/x)/2;
        while(y<x)
        {
               x=y;
               y=(x+N/x)/2;
        }
        return x*x;
 }

但是似乎内置的平方根函数无论如何都更快。我刚刚测量了两者的运行时间。

class Square{
        public static void main(String[] args)
        {
                long startTime = System.currentTimeMillis();
                System.out.println(squareLessThanN(149899437943L));
                long endTime   = System.currentTimeMillis();
                long totalTime = endTime - startTime;
                System.out.println("Running time is "+totalTime);

                startTime = System.currentTimeMillis();
                System.out.println(normal(149899437943L));
                endTime   = System.currentTimeMillis();
                totalTime = endTime - startTime;
                System.out.println("Running time is "+totalTime);

        }
        public static long squareLessThanN(long N)
        {
                long x=N;
                long y=(x+N/x)/2;
                while(y<x)
                {
                        x=y;
                        y=(x+N/x)/2;
                }
                return x*x;
        }
        public static long normal(long N)
        {
                long square = (long)Math.sqrt(N);
                return square*square;
        }
}

输出结果为：

149899060224
Running time is 1
149899060224
Running time is 0

- Anil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- laune · Accepted Answer

注意：能够使用机器指令执行sqrt运算的处理器将足够快。毫无疑问，它的(微)程序采用了牛顿-拉弗森算法，这个算法具有二次收敛性，每次迭代都会使准确数字的数量翻倍。

因此，像这样的想法并不值得追求，尽管它们使用了平方等良好的特性。(请参见下一个提案)

// 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 的平方数。