modを使った平方数の効率的な判定と可視化 - Qiita

概要 平方数の判定を mod を使うと効率よくできるという記事 を5年くらい前に @hnw が ブログでまとめてた 。私は 数論をあまり知らないので、手を動かしながら確かめたい(Python3 on Google Colab)。 「平方数の mod 256 の値は 44 種類しかない」という性質がある。 これを逆に使う。「ある数 N を mod 256 してみて 結果が 44 種類のどれにも該当しないなら Nは平方数でない」を判定の先頭に配置すると、 (256-44)/256 ≒ 83% くらいの確率で 平方数でないと早めに判定ができる。 mod 256 って結局 0xff との ANDというビット演算なので、高速で嬉しい。 44種類？ mod 256だと 44種類だし mod 100 だと 22種類だし(出典:Wikipedia)、mod 19 だと 10種類らしい。これを確かめよう。