1

私が尋ねているのは、この非常に人気のある質問の重複ではありません。ランダムに選択された入力に対して、いくつかの簡単なテストを実行できます。「正方形ではない」と言わない場合は、平方根の計算を実行する必要があります (私自身も解決策を試しました)。

テストする数値が単純な数列に由来する場合、前の (近似) 平方根を使用できるため、状況は異なります。自明なシーケンスの場合、それも自明です。たとえば、

long sqrt = 1;
for (long i=1; i<limit; ++i) {
   if (sqrt*sqrt == i) {
       handleSquare(i);
       ++sqrt;
   }
}

私の質問は、次のようなより複雑なシーケンスに対して何ができるかです

x[i] = start + i*i;

また

x[i] = start - i*i*i;

ニュートンの方法を考えていますが、高速にする方法がわかりません (除算はかなり高価な操作であるため)。

4

1 に答える 1

0

アルゴリズムをどのようなシーケンスに適用しますか? 以下は、 x[i] が発散するが速すぎない場合にうまく機能するソリューションです。

たとえば、

x[i] = a*i^p + o(i^p)

そして、私は十分に大きいので、あなたは持っているでしょう

x[i+1]-x[i] ~ p * a * i^{p-1}.

y[i] が次のような最大の整数を表す場合、

y[i]^2 <= x[i]

それからあなたは持っています

y[i] ~ sqrt(a) i^{p/2}

と

y[i+1]-y[i] ~ 1/(2 y[i]) * (x[i+1]-x[i]) ~ p/2 * sqrt(a) i^{p/2-1}

したがって、これを y[i+1] の推測として取得し、正しい値に更新することができます。これにより、反復を節約できます。

一般に、いつでも式を使用できます

y[i+1]-y[i] ~ 1/(2 y[i]) * (x[i+1]-x[i])

推測ですが、これは x[i+1]-x[i] が y[i]^2 に対して、つまり x[i] に対して小さい場合にのみ役立ちます。の（正確な）2次展開を使用して式を少し改善することも価値があるかもしれません

y[i+1]^2 = y[i]^2 + 2y[i](y[i+1]-y[i]) + (y[i+1]-y[i])^2

y[i+1] の推測を改善するため。

i が大きいときに x[i] が制限されたままの場合、または x が指数関数的に速く発散する場合、これはうまく機能しないことに注意してください。

于 2015-04-27T09:13:21.370 に答える