整数の平方根が整数であるかどうかを確認するより速い方法はありますか?

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

概要

提供されている C/C コードは、高度に最適化された判断方法を提供します。整数の平方根自体が整数である場合。このコードはさまざまな最適化を利用して、組み込み Math.sqrt() 関数を使用する基本的なアプローチと比較してパフォーマンスを大幅に向上させます。

実装の詳細

1. クイック障害チェック: コードはまず一連の簡単なチェックを実行して、平方根が整数にならないケースを特定します。整数の符号とビットパターン。これらのチェックのいずれかが失敗した場合、関数はすぐに false を返します。
2. Modulo 255 Check: 非正方形をさらに除外するために、コードは 255 を法とする整数 (3 つの素数の積) を計算します。数値) を調べ、結果が正方形ではないことがわかっているかどうかを確認します。この目的には、事前計算されたテーブル bad255 が使用されます。
3. 4 の累乗の除算: このコードは、バイナリ検索を使用して入力整数から 2 と 4 の累乗を除算し、効果的に数値を削減します。問題のサイズ。
4. 最終チェック (ヘンゼルの補題にヒントを得た): 最後のステップでは、ヘンセルの補題にヒントを得た反復プロセスを使用して、縮小された整数の平方根を計算します。このプロセスは初期推定から始まり、ビットごとの演算とモジュロ トリックを使用して反復的に精度を高めます。

Math.sqrt() の改善点

提供されたコードは、基本的なコードよりも速度が大幅に向上します。 Math.sqrt() を使用するアプローチ。さまざまな最適化を適用し、数学的特性を利用することにより、コードは、特に大きな整数の場合に、整数の平方根をより高速に決定できます。

複雑さの分析

コードの時間計算量は、次の数に影響されます。最終ステップで必要な反復。ほとんどの場合、少数の反復 (多くの場合 10 未満) で十分です。したがって、全体的な複雑さはおよそ O(1) です。

使用法

このコードは、パラメータとして整数を受け取り、true を返す square() 関数を提供します。完全な正方形の場合は false、それ以外の場合は false。任意の C/C プログラムに簡単に統合して、整数の平方根を迅速かつ効率的にチェックできます。

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