19/02/02 13:18:27.64 CwD+xRo8.net
平方数かどうかを高速に判定する方法 - hnwの日記
URLﾘﾝｸ(hnw.hatenablog.com)
GNU MPのmpz_perfect_square_p関数の実装
GNU MPのソースコードを確認してみたところ、次のような処理だとわかります。
引数nのmod 256を計算し、平方数ではない数を判定する
平方数のmod 256は44種類の値しか出現しないので、入力の82.8%は平方数でないと判定できる
同様に入力nのmod 9, 5, 7, 13, 17（64-bitシステムではmod 97も）を計算し、平方数ではない数を判定する
これにより入力の99.25%（64-bitシステムでは99.62%）について平方数でないと判定できる
最後に、平方根を計算して平方数かどうか確認する
平方数ではない数の多くを事前にふるい落とし、判定できなかった数だけ真面目に平方根を求める、という方針だとわかります。
もちろん、GNU MPの場合のmod pの選び方は多倍長整数演算ならではだと言えます。
mod 256はサイズNにかかわらずO(1)で計算できるので、最初に行うことで全体の高速化に貢献できます。
また、2ステップ目の計算も2^24-1 = 9 * 5 * 7 * 13 * 17 * ...であることを利用し、多倍長整数であっても比較的高速に計算できるような実装になっています。
10進整数でmod 9を求める場合に全部の桁を足し合わせてからmod 9しても同じ結果になるのと同様、
下位から24bit区切りの数を足し合わせてからmod 2^24-1を計算することで、元の数のmod 2^24-1が計算できるのです。