加速互除法
数論入門―証明を理解しながら学べる (ブルーバックス) を見て、加速互除法というユークリッドの互助法の高速化ネタを知りました。
剰余を絶対値が最小になる取り方で与えると、パラメータの減りが速くなるとのこと。
なるほどーと思って実装してみたのですが…
-- (最大公約数, ループ回数) gcd1 x 0 k = (x, k) gcd1 x y k = gcd1 y r (k+1) where r = x `mod` y gcd2 x 0 k = (x, k) gcd2 x y k = gcd2 y r' (k+1) where r = x `mod` y r' = min r (y-r) main = print . sum $ [ snd (gcd2 x y 0) | x <- [1..1000], y <- [1..x] ]
確かにループする回数は減っているんだけど、実行時間計ったら min を取る分遅くなってた。最適化オプションつけてコンパイルすると同じぐらい。有意な改善結果は得られなかった。うまい実装はなさそうだけどなぁ。
gcd1: 2697262 real 0m7.024s user 0m6.980s sys 0m0.044s gcd2: 2088780 real 0m8.161s user 0m8.141s sys 0m0.020s
つか組み込み関数の gcd が死ぬほど速いんですけど…。
追記
Cで試しても同じような結果になった。うーむ。