27

a2 つの整数とが与えられた場合、 のようなb別の整数があるかどうかをテストする効率的な方法はありますか?na ≤&nbsp;n2 < b

を知る必要はありません。そのようなものがn少なくとも 1 つ存在するかどうかだけです。そのため、区間内の数値の平方根を計算することは避け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)。したがって、この事前計算は、平方根を使用せずに、1 つの整数積といくつかの加算と減算だけで実行できます。

a と b がほぼ同じである場合でも、下位 2 進数を調べるトリックを事前計算として使用して、それらの間に正方形がないことを知ることができます。しかし、それらは非常に接近している必要があるため、この事前計算は価値がない場合があります。

これらの事前計算が決定的でない場合、他のすべての解、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 が無制限の整数 (1000 桁など) の場合です。しかし、時代遅れではない通常のコンピュータでの通常サイズの整数の場合、

于 2010-06-29T13:31:35.077 に答える
19

下の数の平方根を取得します。これが整数の場合は完了です。それ以外の場合は、数値を切り上げて 2 乗します。これが b より小さい場合、真です。

この方法で計算する必要があるのは、1 つの平方根だけです。

a が b と等しい場合の問題を回避するために、最初にそれを確認する必要があります。このケースは常に false です。

于 2010-06-29T12:42:48.620 に答える
4

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

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 の場合、yes が出力されます。

そうでなければ出力番号。

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

それとも、a と b の平方根も計算するのを避けたかったのでしょうか?

二分探索と同様の方法を使用すると、平方根の計算を完全に回避できます。

n、n = 1 の推測から始めて、n 2を計算します。

a <= n < b の場合、停止できると考えてください。

n < a < b の場合、推測 n を 2 倍にします。a < b < n の場合は、現在の + 前回の推測の平均に近づけます。

これは O(logb) 時間になります。

于 2010-06-29T12:32:00.530 に答える
0

JDunkerleyの優れたソリューション（+1）に加えて、テストが必要な改善の可能性があり、整数平方根を使用して整数平方根を計算します。

于 2010-06-29T14:00:55.630 に答える
0

なぜ平方根を完全に避けたいのですか？これを解決する最も効率的な方法に到達する前でさえ、2平方根のみを必要とするメソッドを見てきました。これはO（1）時間で行われるため、改善を期待できる場合は、計算時間を節約するよりも、考えるのに時間がかかるように思われます。私が間違っている？

于 2010-06-29T14:24:49.017 に答える
0

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;
}
于 2010-06-29T13:53:59.907 に答える