大きな数が完全二乗であるかどうかを効率的に判断するにはどうすればよいでしょうか?

プログラムの先頭で、操作を高速化するために事前フィルタリングを実行し、負の数や最後の 4 桁が 0 である数値など、明らかな非平方数をフィルタリングして除外します。 、および特定の要件を満たす最後の 2 桁の数字 (10 進数で 5 または 8)。 0 については、平方数と考えてください。

次に、ビット単位の手法を使用して、モジュロ 255 = 3 = 3 5 17 の剰余が平方数であるかどうかを確認します。配列 bad255 は、各剰余が平方数であるかどうかを記録します。テーブルの上に。

プレフィルターを通過した数値については、商が奇数になるまで 2 のすべてのべき乗で (二分探索法で) 除算します。

最後のステップは、ヘンゼルの補題と同様の方法を使用して平方根を近似することです。内側のループは、開始配列によって指定された初期値で始まり、sqrt (mod 8192) の近似値が得られます。この近似は、ビットごとのトリックを使用して速度を向上させ、連続的な計算を通じて継続的に改善されます。

このメソッドの大まかな構造は次のとおりです。

1. 明らかな非平方数を除去するためのプレフィルター。
2. 255 を法とした剰余が平方数であるかどうかを確認します。
3. 2 の累乗で割ります。
4. ヘンゼルの補題の変形を使用して平方根を近似的に計算します。

このアルゴリズムの作成者が、他の方法よりも 35% 高速に実行できると主張していることは注目に値します。

以上が大きな数が完全二乗であるかどうかを効率的に判断するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。