加速互除法・拡張ユークリッドの互除法 続報

IO ()さんのアドバイスにより、拡張ユークリッドの互除法と加速互除法を合体させられました。
……というより、除算アルゴリズムから見て、どうみてもdiv1の定義が間違ってるのにそれを見逃していたってどうなんだ……orz
では、載せます。

-- 剰余の絶対値が少ない方を取るmodとdiv
div1 a b  = (a - (mod1 a b)) `div` b
mod1 a b = ((a + b2) `mod` b) - b2 where b2 = (b-1) `div` 2
divMod1 a b = (div1 a b, mod1 a b)

-- 加速互除法
euclid a 0 = (abs a)
euclid a b = euclid b (mod1 a b)

-- 拡張ユークリッドの互除法
euclidEx a b  = f a b 1 0 0 1
  where f r 0  a  _  b  _ = ((a, b), r)
        f x y a0 a1 b0 b1 = f y r a1 (a0-q*a1) b1 (b0-q*b1)
          where (q, r) = divMod1 x y

--回数計測用 (最大公約数, 呼び出し回数)を返す
gcd' x y = f 0 x y
  where f n x 0 = ((abs x), n+1)
        f n x y = f (n+1) y (x `mod` y)

euclid' x y = f 0 x y
  where f n x 0 = ((abs x), n+1)
        f n x y = f (n+1) y (x `mod1` y)

実行結果は、はしょります。……結果的には前回のと同じだもん。

IO ()さん、ありがとうございました！