Prime - ﾕﾕﾕﾕﾕ

フェルマーの小定理とミラーラビン素数判定法の Elixir による実装をライブラリにして公開した。

もとは SICP を読んで Scheme で実装していたものを、 Elixir でも書いてみたいなとおもって遊びでやってみただけだった。枯れたアルゴリズムで、新奇性もないわけで、完全に趣味で再実装していただけ。

Ruby であれば標準ライブラリに Prime がはいっているし、当然 Elixir にも同等のものがあるんだろうとみていた。作るのはすぐにできてしまって、先行ライブラリを探して実装の違いをみてみようかな、と調べ始めてみた。しかし簡単に検索してもそれらしきものは見当たらず、 hex.pm で探してもなさそう。加えて Erlang の関数にもそれらしいものは存在しなそうにみえた。であれば公開してしまってもいいか、となったのが経緯である。

ドキュメントを書き上げるのがたいへんだった。動かすのはそう難しくなかったはずなのに、それがどうして正しく動くかの根拠を自分の言葉で説明するのに苦労するというのは、理解が浅いことのあらわれにほかならないな、とおもいながら、あらためて定理をよく観察して、証明を追って、自分なりの説明はあたえられたとおもう。そうして書き上げたドキュメントが hexdocs.pm のカッコいいフォーマットでホストしてもらえるのはたいへん達成感がある。それがこれになる。

https://hexdocs.pm/prime/api-reference.html

実装にしても、理論のとおりに作るのは難しくないが、あらためて眺めてみると僕には異形のアルゴリズムにみえる。素数判定器が確率論的に動作するというのもそうだし、加えて広い範囲からランダムに選んだ数字が素数であることに期待してしまうことができる、というのもすごいことだ。実はそこをよく踏まえずに作っていたのだが、ドキュメンテーションのためにこの根拠を再検討して、それが素数定理という美しい定理に支えられていることがわかった。実装は変わらないのに、それを理解したうえで眺めるとますます美しいコードにみえる。異形であって、かつ美しいというのが、僕にとってはいままでにないアルゴリズムの形式で、新しいパラダイムに視野が開かれたのも嬉しい。

素数ライブラリとしてはエラトステネスのふるいも実装していいような気もしつつ、また実際に実装することもできるのだが、フェルマー法とミラーラビン法に並べたときに、スピードがあまりに見劣りするので、含めなかった。 ruby/prime では 10⁶ くらいまでは即座にレスポンスするいっぽうで、僕の実装では 10⁵ ですでにラグりはじめる。 ruby の実装をみると、なにか僕の知らない定理が背後にありそうな気がするが、これはコードを読んでもわかるものではない。いまはわからないが、そのうちなにかの拍子に知ることになりそうな気がする。そうおもっていったん寝かせてみる。