5

頼れるかな 

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

また 

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

が完全平方かどうかを確認するには? なぜですか、そうでないのですか？
int a判断する数字です。Visual Studio 2005 を使用しています。

編集：これらすべての迅速な回答に感謝します。float 型の比較に頼ることができないことがわかりました。(上記のように書いた場合、最後はa暗黙的に float にキャストされますか?) 

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

その値をどのくらい小さくする必要がありeますか?

Edit2:ねえ、比較部分は脇に置いて、(int)が必要かどうかを判断してみませんか? ご覧のとおり、正方形の場合、違いは大きいかもしれません。しかし、それがなければ、非正方形の違いは小さいかもしれません. おそらくどちらもしないでしょう。:-(

4

12 に答える 12

15

実際、これは C++ ではなく、数学の問題です。

  1. 浮動小数点数では、決して等値に頼るべきではありません。a == b をテストする場合は、abs(a - b) < eps に対してテストするだけです。ここで、eps は、適切な近似値として扱う小さな数値 (例: 1E-6) です。
  2. テストしている数値が整数の場合、ウィキペディアの整数平方根に関する記事に興味があるかもしれません

編集：

クルーガーが言ったように、私がリンクした記事は何も答えません。確かに、そこにはあなたの質問に対する直接的な答えはありません、フォエニー。あなたが抱えている根本的な問題は浮動小数点の精度であり、おそらく問題の数学的な背景が必要だと思いました。

せっかちな方のために、この記事にはisqrt の実装に関する長い議論へのリンクがあります。それは、彼の回答に投稿されたコード karx11erx に要約されます。

unsigned long に収まらない整数がある場合は、自分でアルゴリズムを変更できます。

于 2009-09-09T09:51:29.320 に答える
5

浮動小数点精度に依存したくない場合は、整数演算を使用する次のコードを使用できます。

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;
}
于 2009-09-09T10:10:37.040 に答える
2

あなたの質問はすでに回答されていますが、ここに実用的な解決策があります.

「完全平方」は暗黙的に整数値であるため、整数平方根関数を使用してテストする値の整数平方根を決定することにより、浮動小数点形式に関連する精度の問題を簡単に解決できます。その関数はr、値の最大数をv返します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;
}
于 2009-09-09T10:15:29.597 に答える
2

同じ計算を 2 回行わないように、一時的な数値を使用して計算します。

 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
 }
于 2009-09-09T09:48:23.283 に答える
1

式に従わなかった、申し訳ありません。ただし、浮動小数点数を整数型にキャストすることで整数かどうかを簡単に確認し、結果を浮動小数点数と比較できます。そう、

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

当然、これは、整数型の範囲内に収まることがわかっている値を使用している場合にのみ実行可能です。しかし、その場合、この方法で問題を解決でき、数式の固有の複雑さを節約できます.

于 2009-09-09T09:53:53.157 に答える
1

reinier が言うように、最も近い整数に丸めるには 0.5 を追加する必要があるため、次のようになります。

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

これが機能するには、 が完全平方の場合bの平方根に (正確に) 等しくなければなりません。ただし、これを保証することはできないと思います。それが 64 ビットで32 ビットだとします (それは許されると思います)。次に、2 ^ 60 のオーダーになる可能性があるため、その平方根は 2 ^ 30 のオーダーになります。ただし、aは仮数部に 24 ビットしか格納しないため、丸め誤差は 2^(30-24) = 2^6 のオーダーになります。これは 1 より大きいため、間違った整数が含まれている可能性があります。たとえば、上記のコードは= (2^30+1)^2 を完全な正方形として識別していないと思います。aaintfloatafloatba

于 2009-09-09T14:43:21.420 に答える
0

フロートとの等価性をテストするべきではないと指摘する人もいますが、完全平方の特性を利用する機会を逃していると思います。まず、計算されたルートを再二乗しても意味がありません。aが完全平方の場合、sqrt(a)は整数であり、以下を確認する必要があります。

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

ここでeは十分に小さく設定されています。平方根を取る前に、非平方として交差できる整数もいくつかあります。ウィキペディアを確認aすると、正方形になるためのいくつかの必要条件が表示されます。

平方数は、底が 10 の数字 00、1、4、6、9、または 25 でのみ終了できます

a % 4 == 1 or 0別の簡単なチェックは、ルートを取る前にそれを確認することです。

(2n)^2 = 4n^2 なので、偶数の二乗は偶数です。
(2n + 1)^2 = 4(n^2 + n) + 1 なので、奇数の 2 乗は奇数です。

これらは基本的に、根をとる前に整数の半分を削除します。

于 2009-09-09T17:33:54.007 に答える
0

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;   
}
于 2009-09-09T16:02:23.600 に答える
-2

まず基本:

計算で数値を (int) すると、すべてのカンマ後のデータが削除されます。私のCを正しく覚えていれば、計算に(int)がある場合(+/-*)、他のすべての数値は自動的にintと推定されます。

したがって、あなたの場合、関連するすべての数値に浮動小数点数が必要です。そうしないと、データが失われます。

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

あなたが行きたい道です

于 2009-09-09T09:47:14.080 に答える
-2

浮動小数点演算は本質的に不正確です。

したがって、次のコードを検討してください。

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 と等しくないことは十分に明らかです。

于 2009-09-09T09:51:49.620 に答える