加速互除法

数論入門―証明を理解しながら学べる (ブルーバックス) を見て、加速互除法というユークリッドの互助法の高速化ネタを知りました。
剰余を絶対値が最小になる取り方で与えると、パラメータの減りが速くなるとのこと。
なるほどーと思って実装してみたのですが…

-- (最大公約数, ループ回数)
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で試しても同じような結果になった。うーむ。