Ruby の prime が爆速化した件

Ruby の標準添付ライブラリーが次々と gem 化している。
gem 化すると，Ruby バージョンに縛られずにアップデートすることができる。

prime 0.1.2 リリース

さて，昨日（2020-12-09）Ruby の素数ライブラリー prime の新しい版（バージョン 0.1.2）がリリースされた。
何が変わったのだろうか？
prime のリポジトリー を見ても CHANGE.txt や HISTORY.txt の類は無いが，コミット一覧 に

Optimize Integer#prime?

というコミットメッセージを見つけた。
ん？　もしや？　コミットを覗くと，冒頭に MILLER_RABIN_BASES などという定数が定義されている。
やはりアレだ。ミラー–ラビン素数判定法 を使って素数判定を高速化したんだ。

ベンチマーク

素数判定プログラムのベンチマークテストはなかなか難しい。判定する数によって処理時間が大きく変わりうるから。
しかし，ここでは難しいことは考えず，昔作ったプログラムを一つだけ引っ張り出して，time コマンドで時間を測ってみた。

これはかつて以下の記事で提示したコードの一つ。
Ruby で百世紀までの素数日リスト - Qiita

百世紀までの素数日（解説は上の記事を参照）をテキストファイルに書き出すもの。
当然，大量の素数判定が行われる。

require "date"
gem "prime", "0.1.1"
require "prime"

def prime_dates(start_year, end_year)
  result = []
  days = [*1..31].reject{ |day| day.even? || day % 5 == 0 }
  start_year.upto(end_year) do |year|
    1.upto(12) do |month|
      days.each do |day|
        next unless Date.valid_date?(year, month, day)
        if (year * 10_000 + month * 100 + day).prime?
          result << "%04d-%02d-%02d" % [year, month, day]
        end
      end
    end
  end
  result
end

IO.write "prime_dates.txt",
  prime_dates(1, 10_000).join("\n") + "\n"

2 行目の

gem "prime", "0.1.1"

で prime gem のバージョンを 0.1.1 に固定している。
ここを 0.1.2 にしたものと両方で測ってみる。

0.1.1	0.1.2
19.4 sec	3.4 sec

うひょーっ！　5 倍速以上ですかい。