平方数かどうかを高速に判定する方法

平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、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関数として利用できます）。本稿ではこの実装で使われている工夫を紹介します。