完全二乗と整数: 数値の探索

与えられた数値が完全二乗であるかどうかを判断することは、最初は簡単そうに思えます。しかし、大きな整数や浮動小数点計算の複雑さを考慮すると、その課題はより明らかになります。

整数ベースのアプローチ

差し迫った必要性がない場合速度を向上させるために、整数ベースのアプローチは完全二乗をチェックする信頼性の高い手段を提供します。平方根計算のバビロニア アルゴリズムからインスピレーションを得たこれらのメソッドは、初期近似を反復的に改良することで最終的に精度が得られるという考えに基づいています。

具体的には、次の Python 関数 is_square() がこれを使用しています。戦略:

def is_square(apositiveint):
  x = apositiveint // 2
  seen = set([x])
  while x * x != apositiveint:
    x = (x   (apositiveint // x)) // 2
    if x in seen: return False
    seen.add(x)
  return True

このアプローチは、入力 apositiveint の半分として定義される初期近似 x から始まります。次に、反復プロセスに入り、真の平方根 apositiveint に収束するまで x が変更されます。

収束を確実にするために、現在の近似値 x がセットに保存され、以前の出現がないか確認されます。 。繰り返しが検出された場合は、収束が欠如していることを示し、関数は False を返します。それ以外の場合、x * x が apositiveint に等しい場合に True を返します。

検証の例

このメソッドの有効性を説明するために、次の例を考えてみましょう。

for i in range(110, 130):
   print(i, is_square(i))

このループは、110 から 129 までの整数の範囲を繰り返し、各数値が完全な正方形であるかどうかをチェックします。出力は関数の精度を確認し、完全な正方形でない場合は false が出力され、完全な正方形の場合は true が出力されます。

浮動小数点に関する考慮事項

注意が必要です浮動小数点計算は明らかな解決策を提供するかもしれませんが、誤った結論につながる可能性のある丸め誤差のリスクをもたらします。整数の乗算と累乗は正確な演算であるため、整数ベースのアプローチにより、特に大きな数値の精度が保証されます。

Gmpy Library

速度を優先する場合は、gmpyライブラリは、整数関数の非常に効率的な実装を提供します。特に、その is_square() メソッドは大幅なパフォーマンスの向上をもたらします:

import gmpy

gmpy.is_square(x**7)
gmpy.is_square(x**7   1)

非常に大きな整数に対して実行されるこれらの操作は、gmpy ライブラリの並外れた機能を示しています。ただし、これを使用すると、計算負荷の高いアプリケーションの実行時の複雑さとメモリ使用量に関する懸念が生じる可能性があります。