27

给定两个整数a和b，是否有一种有效的方法来测试是否存在另一个n整数？a ≤&nbsp;n2 < b

我不需要知道n，只知道是否存在至少一个这样的n，所以我希望避免计算区间内任何数字的平方根。

虽然测试单个整数是否是完美平方比计算平方根更快，但范围可能很大，我也希望避免对范围内的每个数字执行此测试。

例子：

  • intervalContainsSquare(2, 3)=> 假的
  • intervalContainsSquare(5, 9)=> false （注意：9 在此区间之外）
  • intervalContainsSquare(9, 9)=> false（此区间为空）
  • intervalContainsSquare(4, 9)=> true (4 在这个区间内)
  • intervalContainsSquare(5, 16)=> true (9 在这个区间内)
  • intervalContainsSquare(1, 10)=> true（1、4和9都在这个区间内）
4

8 回答 8

26

据我所知，计算一个数字是否是一个平方并不比在困难情况下计算它的平方根快。正确的是，您可以进行预计算以知道它不是正方形，这平均可以节省您的时间。

同样对于这个问题，您可以进行预计算以确定 sqrt(b)-sqrt(a) >= 1，这意味着 a 和 b 相距足够远，以至于它们之间必须有一个正方形。对于某些代数，这个不等式等价于 (ba-1)^2 >= 4*a 的条件，或者如果您希望它采用更对称的形式，则 (ab)^2+1 >= 2*(a +b）。所以这个预计算可以不用平方根，只用一个整数乘积和一些加法和减法来完成。

如果 a 和 b 几乎完全相同，那么您仍然可以使用查看低位二进制数字作为预计算的技巧来知道它们之间没有正方形。但是它们必须非常接近，以至于这种预先计算可能不值得。

如果这些预计算没有定论，那么除了其他人的解决方案之外，我想不出其他任何东西，a <= ceil(sqrt(a))^2 < b。

由于存在正确代数的问题：

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

另外：通常，当 a 很大时，您将使用牛顿法计算 sqrt(a)，或者使用查找表，然后使用几个牛顿法步骤。计算 ceil(sqrt(a)) 原则上比 sqrt(a) 更快，因为浮点运算可以简化为整数运算，并且不需要那么多牛顿方法步骤来确定高精度你只是要扔掉。但在实践中，如果使用在微码中实现的平方根，数值库函数会快得多。如果由于某种原因您没有该微代码来帮助您，那么手动编码 ceil(sqrt(a)) 可能是值得的。也许最有趣的情况是 a 和 b 是无界整数（例如，一千位）。但是对于普通非过时计算机上的普通大小的整数，

于 2010-06-29T13:31:35.077 回答
19

获取较小数字的平方根。如果这是一个整数，那么你就完成了。否则将数字四舍五入并平方。如果这小于 b 则为真。

您只需要以这种方式计算一个平方根。

为了避免出现 a 等于 b 的问题，您应该先检查一下。因为这种情况总是错误的。

于 2010-06-29T12:42:48.620 回答
4

如果你接受计算两个平方根，由于它的单调性，你有这个不等式，它相当于你的开始：

sqrt(a) <= n < sqrt(b)

因此，如果floor(sqrt(a)) != floor(sqrt(b)),floor(sqrt(b)) - 1保证是这样的n.

于 2010-06-29T12:32:47.103 回答
4
  1. 得到较小数字的平方根并将其四舍五入
  2. 取较大数的平方根并将其向下舍入
  3. 如果 1 小于或等于 2，将有一个完美的正方形
于 2010-06-29T12:34:59.073 回答
2

求 sqrt(a) 和 sqrt(b) 的整数部分，比如 sa 和 sb。

如果sa 2 = a，则输出yes。

如果 sb 2 = b 且 sa = sb-1，则输出 no。

如果 sa < sb 输出是。

其他输出编号

您可以优化上述内容以摆脱 sqrt(b) 的计算（类似于 JDunkerly 的答案）。

或者您是否也想避免计算 a 和 b 的平方根？

您可以使用类似于二分搜索的方法完全避免计算平方根。

您从猜测 n 开始，n = 1 并计算 n 2

考虑如果a <= n < b，您可以停止。

如果 n < a < b，则您的猜测 n 加倍。如果 a < b < n，则使其接近当前 + 先前猜测的平均值。

这将是 O(logb) 时间。

于 2010-06-29T12:32:00.530 回答
0

一种方法是使用牛顿法求 的整数平方根。b然后您可以检查该数字是否在该范围内。我怀疑它是否比简单地调用平方根函数更快，但它肯定更有趣：

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}
于 2010-06-29T13:53:59.907 回答
0

除了 JDunkerley 的好解决方案 (+1) 之外，可能还有需要测试并使用整数平方根来计算整数平方根的改进

于 2010-06-29T14:00:55.630 回答
0

为什么你希望完全避免平方根？甚至在你找到解决这个问题的最有效方法之前，你已经看到了只需要 2 个平方根的方法。这是在 O(1) 时间内完成的，所以在我看来，你可能希望做出的任何改进都需要更多的时间来思考，而不是节省你的计算时间。我错了吗？

于 2010-06-29T14:24:49.017 回答