c++ - 我可以依靠它来判断 C++ 中的平方数吗？

Question

我可以依靠吗

sqrt((float)a)*sqrt((float)a)==a

或者

(int)sqrt((float)a)*(int)sqrt((float)a)==a

检查一个数字是否是一个完美的正方形？为什么或者为什么不？
int a是要判断的数字。我正在使用 Visual Studio 2005。

编辑：感谢所有这些快速的答案。我看到我不能依赖浮点类型比较。（如果我如上所述写，最后一个a会被强制转换为隐式浮动吗？）如果我这样做

(int)sqrt((float)a)*(int)sqrt((float)a) - a < e

我应该把这个e值取多少？

Edit2：嘿，我们为什么不把比较部分放在一边，决定是否(int)有必要？如我所见，有了它，正方形的差异可能很大。但没有它，对于非正方形来说，差异可能很小。也许两者都不会。:-(

score 15 · Accepted Answer

实际上，这不是 C++，而是一道数学题。

对于浮点数，您永远不应该依赖相等性。如果您要测试 a == b，只需针对 abs(a - b) < eps 进行测试，其中 eps 是一个很小的数字（例如 1E-6），您可以将其视为足够好的近似值。
如果您要测试的数字是整数，您可能会对有关整数平方根的 Wikipedia 文章感兴趣

编辑：

正如克鲁格所说，我链接的文章没有回答任何问题。当然，菲妮，你的问题没有直接的答案。我只是认为您遇到的根本问题是浮点精度，也许您想要一些数学背景来解决您的问题。

对于不耐烦的人，文章中有一个链接指向关于实现 iqrt 的冗长讨论。归结为他的答案中发布的代码 karx11erx。

如果您有不适合无符号长整数的整数，您可以自己修改算法。

score 5 · Accepted Answer

如果您不想依赖浮点精度，则可以使用以下使用整数数学的代码。

Isqrt 取自这里，为 O(log n)

// Finds the integer square root of a positive number
static int Isqrt(int num)
{
    if (0 == num) { return 0; }  // Avoid zero divide
    int n = (num / 2) + 1;       // Initial estimate, never low
    int n1 = (n + (num / n)) / 2;
    while (n1 < n)
    {
        n = n1;
        n1 = (n + (num / n)) / 2;
    } // end while
    return n;
} // end Isqrt()

static bool IsPerfectSquare(int num)
{
    return Isqrt(num) * Isqrt(num) == num;
}

score 2 · Accepted Answer

您的问题已经得到解答，但这是一个可行的解决方案。

您的“完美平方”是隐含的整数值，因此您可以通过使用一些整数平方根函数来确定要测试的值的整数平方根，轻松解决浮点格式相关的精度问题。该函数将返回r值vwhere的最大数字r * r <= v。一旦你有了r，你只需要测试是否r * r == v。

unsigned short isqrt (unsigned long a)
{
    unsigned long rem = 0;
    unsigned long root = 0;

    for (int i = 16; i; i--) {
        root <<= 1;
        rem = ((rem << 2) + (a >> 30));
        a <<= 2;
        if (root < rem)
            rem -= ++root;
    }

    return (unsigned short) (root >> 1);
}

bool PerfectSquare (unsigned long a)
{
    unsigned short r = isqrt (a);

    return r * r == a;
}

score 2 · Accepted Answer

不要两次做同样的计算，我会用一个临时数字来做：

 int b = (int)sqrt((float)a);
 if((b*b) == a)
 {
     //perfect square
 }

编辑： dav 提出了一个很好的观点。而不是依靠演员，你需要先四舍五入

所以应该是：

 int b = (int) (sqrt((float)a) + 0.5f);
 if((b*b) == a)
 {
     //perfect square
 }

score 1 · Accepted Answer

我会做。

// sqrt always returns positive value. So casting to int is equivalent to floor()
int down =  static_cast<int>(sqrt(value));
int up   = down+1;                           // This is the ceil(sqrt(value))

// Because of rounding problems I would test the floor() and ceil()
// of the value returned from sqrt().
if (((down*down) == value) || ((up*up) == value))
{
     // We have a winner.
}

score 1 · Accepted Answer

正如 reinier 所说，你需要加上 0.5 以确保它四舍五入到最接近的整数，所以你得到

int b = (int) (sqrt((float)a) + 0.5f);
if((b*b) == a) /* perfect square */

为此，b必须（完全）等于a如果a是完美平方的平方根。但是，我认为您不能保证这一点。假设int是 64 位和float32 位（我认为这是允许的）。那么a可以是 2^60 的数量级，所以它的平方根是 2^30 的数量级。但是，afloat仅在有效数中存储 24 位，因此舍入误差的阶数为 2^(30-24) = 2^6。这大于 1，因此b可能包含错误的整数。例如，我认为上面的代码没有将a= (2^30+1)^2 识别为完美正方形。

score 1 · Accepted Answer

我没有按照公式，我道歉。但是您可以通过将浮点数转换为整数类型并将结果与浮点数进行比较来轻松检查浮点数是否为整数。所以，

bool isSquare(long val) {
    double root = sqrt(val);
    if (root == (long) root)
        return true;
    else return false;
}

当然，这只有在您使用您知道将适合整数类型范围的值时才可行。但在这种情况下，您可以通过这种方式解决问题，从而节省数学公式固有的复杂性。

score 0 · Accepted Answer

虽然其他人指出您不应该使用浮点数来测试相等性，但我认为您错过了利用完美正方形属性的机会。首先，对计算的根进行重新平方是没有意义的。如果a是一个完美的正方形，那么sqrt(a)是一个整数，你应该检查：

b = sqrt((float)a)
b - floor(b) < e

wheree设置得足够小。在取平方根之前，您还可以将许多整数作为非平方来交叉。查看维基百科，您可以看到一些必要条件a：

平方数只能以 00、1、4、6、9 或 25 结尾，以 10 为底

另一个简单的检查是a % 4 == 1 or 0在扎根之前查看它，因为：

偶数的平方是偶数，因为 (2n)^2 = 4n^2。
奇数的平方是奇数，因为 (2n + 1)^2 = 4(n^2 + n) + 1。

这些基本上会在取任何根之前消除一半的整数。

score 0 · Accepted Answer

更明显的是，如果速度较慢 - O(sqrt(n)) - 方式：

bool is_perfect_square(int i) {
    int d = 1;
    for (int x = 0; x <= i; x += d, d += 2) {
        if (x == i) return true;
    }
    return false;   
}

score 0 · Accepted Answer

最干净的解决方案是使用整数 sqrt 例程，然后执行以下操作：

bool isSquare( unsigned int a ) {

  unsigned int s = isqrt( a );
  return s * s == a;

}

这将在整个 int 范围内以完美的精度工作。几个案例：

a = 0, s = 0, s * s = 0 (add an exception if you don't want to treat 0 as square)  
a = 1, s = 1, s * s = 1  
a = 2, s = 1, s * s = 1  
a = 3, s = 1, s * s = 1  
a = 4, s = 2, s * s = 4  
a = 5, s = 2, s * s = 4

当您接近 int 大小的最大值时，也不会失败。例如对于 32 位整数：

a = 0x40000000, s = 0x00008000, s * s = 0x40000000  
a = 0xFFFFFFFF, s = 0x0000FFFF, s * s = 0xFFFE0001

使用浮点数会遇到许多问题。您可能会发现sqrt( 4 ) = 1.999999...和类似的问题，尽管您可以四舍五入而不是使用floor().

更糟糕的是，浮点数只有 24 个有效位，这意味着您不能将任何大于 2^24-1 的 int 转换为浮点数而不会丢失精度，这会引入误报/误报。不过，使用双精度数来测试 32 位整数应该没问题。

但请记住将浮点 sqrt 的结果转换回 int 并将结果与原始 int 进行比较。浮点数之间的比较从来都不是一个好主意。即使对于有限范围内的 x 平方值，也不能保证sqrt( x ) * sqrt( x ) == x或sqrt( x * x) = x。

score -2 · Accepted Answer

先说基础：

如果您在计算中（int）一个数字，它将删除所有逗号后数据。如果我没记错我的 C，如果您在任何计算 (+/-*) 中有 (int)，它将自动假定所有其他数字的 int。

因此，在您的情况下，您希望在涉及的每个数字上浮动，否则您将丢失数据：

sqrt((float)a)*sqrt((float)a)==(float)a

是你想走的路

score -2 · Accepted Answer

浮点数学本质上是不准确的。

所以考虑这段代码：

int a=35;
float conv = (float)a;
float sqrt_a = sqrt(conv);
if( sqrt_a*sqrt_a == conv )
    printf("perfect square");

这将发生：

a = 35
conv = 35.000000
sqrt_a = 5.916079
sqrt_a*sqrt_a = 34.999990734

这很清楚 sqrt_a^2 不等于 a。

c++ - 我可以依靠它来判断 C++ 中的平方数吗？

12 回答 12

Related

Reference