[解決済み] ある数字が完全平方であるかどうかをチェックする

質問

ある数字が完全な正方形であるかどうかを調べるにはどうしたらよいでしょうか。

速度は気にせず、とりあえず、作業しています。

どのように解決するのですか？

任意の浮動小数点演算に依存した場合の問題点 ( math.sqrt(x) または x**0.5 ) が正確であるかどうかはわからないということです (十分に大きな整数の場合 x ではそうではなく、オーバーフローする可能性さえあります）。幸いにも (急がなければ;-) 以下のような多くの純粋な整数のアプローチがあります...。

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

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

ヒント: これは平方根のための "Babylonian algorithm" に基づいています。 ウィキペディア . それは は は、計算を完了させるのに十分なメモリがある任意の正の数に対して動作します;-)。

編集 : 例を見てみましょう...

x = 12345678987654321234567 ** 2

for i in range(x, x+2):
   print i, is_square(i)

を実行すると、希望通りに印刷されます（しかも、それなりの時間で;-)。

152415789666209426002111556165263283035677489 True
152415789666209426002111556165263283035677490 False

浮動小数点数の中間結果を基にした解決策を提案する前に、この単純な例で正しく動作することを確認してください -- それは その 難しいことではなく (計算された sqrt が少しずれている場合に備えて、いくつかの追加チェックが必要なだけです)、ただ少し注意が必要なのです。

そして x**7 で試してみて、出てくる問題を回避する賢い方法を見つけてください。

OverflowError: long int too large to convert to float

もちろん、数が増えれば増えるほど、もっともっと賢くならなければなりませんが。

もし私が は を使うでしょう。 gmpy -- を使いますが、これは明らかに私の偏見です;-)。

>>> import gmpy
>>> gmpy.is_square(x**7)
1
>>> gmpy.is_square(x**7 + 1)
0

そうですね、あまりにも簡単なので、ごまかしのように感じます（Python全般に対して私が感じていることと少し似ています;-)--巧妙さはまったくなく、ただ完璧な直接性と単純さ（そしてgmpyの場合は圧倒的な速度;-）...。