問題タブ [perfect-square]

long値が完全な平方であるかどうか（つまり、その平方根が別の整数であるかどうか）を判断するための最速の方法を探しています。

1. 組み込み関数を使って簡単な方法でやったのMath.sqrt() ですが、整数のみのドメインに制限することでもっと速くできる方法があるのではないかと思います。
2. ルックアップテーブルを維持することは実用的ではありません（2乗が2 ⁶³未満の整数が約^231.5あるため）。

これが私が今やっている非常に単純で簡単な方法です：

_{注：私は多くのプロジェクトオイラー問題でこの関数を使用しています。したがって、他の誰もこのコードを維持する必要はありません。そして、この種のマイクロ最適化は実際に違いを生む可能性があります。課題の一部はすべてのアルゴリズムを1分未満で実行することであり、問​​題によってはこの関数を何百万回も呼び出す必要があるためです。}

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

• 0.5徹底的なテストの結果、少なくとも私のマシンでは、Math.sqrt（）の結果に追加する必要がないことがわかりました。
• 高速逆平方根は高速でしたが、n> = 410881の場合は誤った結果になりました。ただし、BobbyShaftoeが示唆しているように、 n<410881の場合はFISRハックを使用できます。
• ニュートン法は、よりも少し遅かっMath.sqrt()た。これはおそらく、Math.sqrt()ニュートン法に似たものを使用しているが、ハードウェアに実装されているため、Javaよりもはるかに高速であるためです。また、ニュートン法では、依然としてdoubleを使用する必要がありました。
• 整数計算のみが含まれるようにいくつかのトリックを使用した修正ニュートン法は、オーバーフローを回避するためにいくつかのハックを必要とし（この関数をすべての正の64ビット符号付き整数で機能させたい）、それでも。よりも低速Math.sqrt()でした。
• バイナリチョップはさらに遅くなりました。バイナリチョップは64ビット数の平方根を見つけるために平均16パスを必要とするため、これは理にかなっています。
• Johnのテストによると、orステートメントの使用は、C ++では、を使用するよりも高速ですが、JavaとC＃では、との間にswitch違いはないようです。orswitch
• また、ルックアップテーブルを作成してみました（64ブール値のプライベート静的配列として）。次に、switchまたはorstatementの代わりに、と言いif(lookup[(int)(n&0x3F)]) { test } else return false;ます。驚いたことに、これは（ほんの少しだけ）遅くなりました。これは、Javaで配列の境界がチェックされるためです。

重複の可能性：
整数の平方根が整数であるかどうかを判断する最速の方法

数が完全な正方形であるかどうかを確認する方法は何ですか？

私はC＃を使用していますが、これは言語に依存しません。

明快さと単純さのためのボーナスポイント（これはコードゴルフを意味するものではありません）。

編集：これは私が予想していたよりもはるかに複雑になりました！倍精度の問題は、いくつかの方法で明らかになります。まず、Math.Sqrtはdoubleを取りますが、これは正確に長く保持することはできません（Jonに感謝します）。

第二に、あなたが巨大でほぼ完全な正方形を持っているとき、doubleの精度は小さな値（.000 ... 00001）を失います。たとえば、私の実装はMath.Pow（10,18）+1のこのテストに失敗しました（私の実装はtrueと報告されています）。

頼れるかな

また

が完全平方かどうかを確認するには? なぜですか、そうでないのですか？
int a判断する数字です。Visual Studio 2005 を使用しています。

編集：これらすべての迅速な回答に感謝します。float 型の比較に頼ることができないことがわかりました。(上記のように書いた場合、最後はa暗黙的に float にキャストされますか?)

その値をどのくらい小さくする必要がありeますか?

Edit2:ねえ、比較部分は脇に置いて、(int)が必要かどうかを判断してみませんか? ご覧のとおり、正方形の場合、違いは大きいかもしれません。しかし、それがなければ、非正方形の違いは小さいかもしれません. おそらくどちらもしないでしょう。:-(

数値が完全な正方形であるかどうかを確認するにはどうすればよいですか？

今のところ、速度は問題ではありません。

最初のn個の完全な正方形のリストをリスト形式で提供するPythonプログラムの作成方法についてアドバイスが必要です。出力は次のようになります。

これは私がこれまでに持っているものです：

次のパートでは、最初のn個の正方形のリストを作成する必要があります。どのように何か提案はありますか？お手数をおかけしますが、よろしくお願いいたします。

整数引数より大きい最初の完全平方を返す関数を作成する必要があります。完全平方は、ある整数の 2 乗に等しい整数です。たとえば、16 = 4 * 4 であるため、16 は完全平方です。ただし、15 = n*n となる整数 n がないため、15 は完全平方ではありません。

これは正しいですか？

forループを使用してVisualBasicで平方数のリストを印刷しようとしています。私は初心者ですが、これはかなり難しいと思います。私が書いているプログラムは、数の二乗のリストを出力することになっています（例：（1、4、9、16など））。

これは、数値が完全な正方形であるかどうかを確認するためのコードです。なぜそれが機能するのですか？

私はPythonを学び始めたばかりで、スキルを磨くためにいくつかの問題を解決し始めましたが、この質問にはかなりこだわっています。

1000までのすべての正の整数を含むリストを作成します。その二乗は、2つの二乗の合計として表すことができます（つまり、p ^ 2 = m ^ 2 + n ^ 2である整数p。ここで、mとnは整数です。 0より大きい。）

ヒント：いくつかのアプローチがあります。すべての平方数のリストがあると便利な場合があります。in演算子が役立つ場合があります。

これまでに思いついたコードは次のとおりです。

これで私が得る問題は、Pythonがこれらの計算を行うのに何年もかかることです（私は約10分待っていましたが、まだ数値を出力しています）。これを解決する方法についてのヒントをいただければ幸いです。

ps主なポイントはリストを使用することです。また、ヒントはソリューション自体よりも高く評価されます。

ありがとう！

数値が完全な二乗でない場合は false を返し、それ以外の場合はルートを返します。しかし、このコードでは常にルートを返します。例: 入力 5、ルート 2。