平方数かどうかを高速に判定する方法 - hnwの日記

平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装

[tanimina]

平方数(完全平方)かどうかの判定が必要なアルゴリズムの実例 http://d.hatena.ne.jp/lemniscus/20130226/1361874593#squfof

[megazalrock]

こういう「不真面目な」発想ってなかなか出てこないんだよな。

[zuborawka]

“mod pを計算すれば平方数でない数が判定できる”ほう

[sstt0001]

平方数かどうかを高速に判定する方法 - hnwの日記 平方数とは、ある整数の平方（＝二乗）であるような自然数のことを言います。つまり、1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かど

[rhosoi]

このレベルの数学なら俺にもわかるぞ(´∀｀)

[stanaka]

数論面白い

[natroun]

これ凄く面白い。mod n でふるいにかけられることをそもそも知らなかった。mod 256 でどうして44種類になるのか知りたい。流石に難しいかな。

[stealthinu]

うー…　なんでn mod 256…で平方数の判定出来るのかわからん。82.8%はそれで判定できる、というところすら。

[hirata_yasuyuki]

こういう記事を読むと、真面目に数学を勉強しておくべきだったなーと若干後悔する。Browsing: “平方数かどうかを高速に判定する方法 - hnwの日記”

[indication]

アルゴリズムの実装って結局のところ、統計に基づく部分が大きいのか

[mas-higa]

"0を除外すると" のところでついて行けなくなった。

[UDONCHAN]

興味深い

[mohno]

多倍長整数演算ライブラリに平方数を判定する関数が用意されているのは、まさに「多倍長整数演算」だからじゃないかなあ。通常の浮動小数演算の範囲なら「平方根の計算」は除算に毛が生えた程度だと思うけど。

[fujigokoro1989]

面白いな。数学って面白いよね。

[yukisalto]

modを使うのね

[zichao]

面白そうだけど、一読して理解できない。。。orz

[Nyoho]

こんなところに平方剰余の話がっ! 平方剰余とその相互法則の話のときに実例として使えるな。

[nekonyantaro]

sqrt計算する前にmodを使って「対象外」のものをなるべくふるい落とす作戦。

[sardine11]

整数論はとっつきやすいけど、激難。でも解けるとすっげー解放感がある学問だなー。おもしろかった！

[I8D]

面白かった！こういうの、どんな人が考えて実装しているんだろう？

[gigi-net]

おもしろい

[goturu]

自分が文系脳であること嫌というほど思い知った

[soramimi-cake]

やばい面白い

[InoHiro]

整数論面白そうだが難しそうだ

[yasudayasu]

引数nのmod 256を計算し、平方数ではない数を判定する 平方数のmod 256は44種類の値しか出現しないので、入力の82.8%は平方数でないと判定できる 同様にmod 9, 5, 7, 13, 17を計算 最後に、平方根を計算して平方数か確認

[shin1x1]

なるほど、面白い。

[imo758]

開閉法を下の桁から行うような感じで何か新技術はできないのだろうか

[kusomamma]

何かに使えそうな気がした

[plank]

　なるほど！