15.5.3 完全平方

入力値が小さい整数に対する剰余平方根になっているかどうかをチェックすると，完全平方数ではない有効小数部を素早く確定することができます。

mpz_perfect_square_p関数はまず最初に入力値の256に対する剰余を求めて，低いバイト値の方を確認します。256の剰余平方根に対しては44種類しかないので，入力値の82.8%は即座に完全平方数ではないということが確定します。

32-bitシステム上では，同様のテストを9, 5, 7, 13，17の剰余に対して行い，結果として入力値の 99.25%が完全平方数ではないことを確定しています。 64-bitシステム上では更に97の剰余テストを加えてこの確率を99.62%まで高めています。

これらの数は2^24-1 (64bitシステムでは2^48-1)の因数になっているものを使っています。さすれば，この剰余は加算を行うだけで高速に導出できます(mpn_mod_34lsub1関数参照)。

ネイルが利用できる場合は，gen-psqr.cプログラムを使って剰余演算の代わりができ，mpn_mod_1関数が使えるようになります。2^24-1や2^48-1でも余分なビットシフトを使ったネイルを用いて同様のことができますが，今のところ実装していません。

どんな場合でも，剰余計算はmpn_mod_34lsub1関数，もしくは mpn_mod_1関数で実行し，テーブル参照で完全平方数でないことを確定します。 “modexact”スタイルの計算を行って，ふさわしい置換テーブルを使うと，乗算は1回だけで済むようになります（詳細はソースコードを参照）。参照テーブルが特別大きいものでなければ，剰余演算もこの組み合わせを使うことでコスト削減できます。 gen-psqr.cではこの手の前処理を全て行っています。

平方根はこのテストを通過した値全てに対して導出できなければなりません。その数は当然，真の平方数でなくてはならず，テストに通過してしまうわずかな小数が出てくるものでもダメです。(即ち，準平方数になる場合もダメ）。

となれば，当然更なる剰余テストが必要になりますが，mpz_perfect_square_p関数ではそのためのコンパクトで効率的なテスト集合だけを利用します。入力値が大きい時には確率的にこの手の追加剰余テストが有効ですが，小さい場合はあまり効果が出ません。入力値における完全平方数 vs. 非平方数の分布を考えてこの手のテストの効率を考える必要があります。