整数の平方根が整数であるかどうかを判断する最速の方法は何ですか?

整数の平方根が整数であるかどうかを判断する最速の方法

問題の説明

Long 整数が完全な 2 乗であるかどうか (つまり、その平方根が別の整数であるかどうか) を判断する最速の方法:

1. 組み込みの Math.sqrt() 関数を使用して実行しましたが、それを行う方法があるかどうか知りたいです整数フィールドを使用することで速度が向上します。


2. ルックアップ テーブルを維持するのは非現実的です (平方が 2⁶³ 未満である整数が約 2^31.5 あるため)。

これが私が現在行っている非常にシンプルで簡単な方法です:

{<br> if (n < 0)</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">return false;

ログイン後にコピー

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{注: 私はこの関数を多くの Project Euler 問題で使用しています。したがって、今後このコードのメンテナンスは行われません。そして、問題によってはこの関数を何百万回も呼び出す必要があるのに対し、各アルゴリズムを完了するのに 1 分もかからないことが課題の一部であるため、この微細な最適化は実際に違いを生む可能性があります。}

---

この問題に対してさまざまな解決策を試しました:

• 徹底的なテストの結果、少なくとも私のマシンでは Math.sqrt() の結果に 0.5 を加算する必要がないことがわかりました。


• 高速逆平方根は Math.sqrt() より高速ですが、n >= 410881 の場合は誤った結果が得られます。ただし、BobbyShaftoe が示唆したように、n
• Newton のメソッドは Math.sqrt() よりもはるかに遅いです。これはおそらく、Math.sqrt() が Newton のメソッドに似たものを使用しているためですが、ハードウェアで実装されているため、Java よりもはるかに高速であるためです。さらに、ニュートン法では依然として倍精度浮動小数点数を使用する必要があります。
正の 64 ビット符号付き整数)、Math.sqrt() よりも遅くなります。

• 二分探索はさらに遅くなります。二分探索では 64 ビット数値の平方根を見つけるのに平均 16 回のパスが必要なため、これは当然のことです。


• John のテストによると、C では or ステートメントを使用した方がスイッチを使用するより高速ですが、Java と C# では or とスイッチの間に違いはないようです。


• また、ルックアップ テーブル (64 個のブール値のプライベート静的配列として) を作成してみました。次に、switch or or ステートメントを使用する代わりに、 if(lookup[(int)(n&0x3F)]) { test } else return false; と言うだけですが、驚いたことに、これは (わずかに) 遅くなります。これは、Java で配列の境界がチェックされるためです。

以上が整数の平方根が整数であるかどうかを判断する最速の方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。