さまざまな整数には、少なくとも1つの完全な正方形が含まれていますか？

Question

2つの整数が与えられます a と b, 、別の整数があるかどうかをテストする効率的な方法はありますか n そのような a ≤ n2 < b?

私は知る必要はありません n, 、少なくとも1つのそのようかどうかのみ n 存在するかどうかにかかわらず、私は望んでいます 正方形の根を計算しないでください 間隔の任意の数字の。

それでも 個々の整数が完全な正方形であるかどうかをテストすると、平方根を計算するよりも速いです, 、範囲が大きい場合があります。また、範囲内のすべての数値に対してこのテストを実行することも避けたいと思います。

例：

• intervalContainsSquare(2, 3) => false
• 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はすべてこの間隔の内側にあります）

Answer 1

数字が正方形であるかどうかを計算すると、私の知る限り、ハードケースでは平方根を計算するよりも速くはありません。真実は、それが正方形ではないことを知るために事前計算を行うことができるということです。

同様に、この問題については、SQRT（B）-SQRT（A）> = 1であると判断するために事前計算を行うことができます。一部の代数では、この不平等は（Ba-1）^2> = 4*a、またはより対称的な形式で必要な場合、（ab）^2+1> = 2*（a +b）。したがって、この事前計算は、正方形の根なしで行うことができ、1つの整数製品といくつかの追加と減算でのみ行うことができます。

aとbがほぼ同じである場合でも、それらの間に正方形がないことを知るために、低次のバイナリ数字を前提条件として見るトリックを使用することができます。しかし、彼らは非常に親密でなければならないので、この事前計算はそれだけの価値がないかもしれません。

これらの事前コンパートが決定的でない場合、私は他のすべての人の解決策以外のことを考えることができません<= 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が多数の場合、Newtonの方法でSQRT（a）を計算するか、ルックアップテーブルに続いていくつかのニュートンのメソッドステップを使用します。浮動小数点算術を整数算術に単純化できるため、SQRT（a）よりも天井（SQRT（a））を計算する方が高速です。あなたはただ捨てるつもりです。しかし、実際には、数値ライブラリ関数は、マイクロコードに実装された四角い根を使用する場合、はるかに高速になる可能性があります。何らかの理由であなたがあなたを助けるためにそのマイクロコードを持っていないなら、それはハンドコードの天井（SQRT（a））に価値があるかもしれません。たぶん、最も興味深いケースは、AとBが固定されていない整数（1000桁など）である場合です。しかし、通常の非肥満コンピューターの通常のサイズの整数の場合、FPUに勝つことはできません。

Answer 2

低い数の平方根を取得します。これが整数である場合、あなたは完了です。それ以外の場合は、数字を丸めて四角い。これがBよりも少ない場合、それは本当です。

この方法で1平方根を計算する必要があります。

AがBに等しい場合の問題を回避するには、最初にそれを確認する必要があります。このケースは常に間違っているためです。

Answer 3

2つの正方形の根の計算を受け入れる場合、その単調性のために、この不平等があります。

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

したがって、場合 floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 そのようなものであることが保証されています n.

Answer 4

1. 低い数の平方根を取得し、それを丸めます
2. より高い数の平方根を取得し、それを丸めます
3. 1が低いまたは等しい2の場合、完全な正方形があります

Answer 5

SQRT（a）とSQRT（b）の積分部分を見つけて、SAとSBなど。

saの場合² = A、次に出力はい。

sbの場合² = bおよびsa = sb-1、その後出力no。

sa <sb出力の場合はい。

その他の出力番号。

上記を最適化して、SQRT（b）の計算を取り除くことができます（JDunkerlyの回答と同様）。

それとも、AとBの正方形の根を計算しないようにしたいですか？

---

バイナリ検索と同様の方法を使用して、正方形の根を完全に計算することを避けることができます。

n、n = 1、およびnの推測から始めます。²

a <= n <bの場合、停止できます。

n <a <bの場合、推測nを2倍にします。 a <b <nの場合、電流 +前の推測の平均に近づきます。

これはo（logb）時間になります。

Answer 6

Jdunkerleyの素晴らしいソリューション（+1）に加えて、テストする必要がある改善が可能になる可能性があります 整数四角の根 整数の正方形の根を計算します

Answer 7

なぜ正方形の根を完全に避けたいのですか？これを解決する最も効率的な方法に到達する前でさえ、2つの平方根しか必要とする方法を見てきました。それはO（1）時間で行われているので、あなたが望むことができる改善は、コンピューティング時間を節約するよりも多くの時間がかかるでしょう。私が間違っている？

Answer 8

1つの方法は、ニュートンの方法を使用して 整数平方根 にとって 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;
}