拡張ユークリッド互除法も再帰で書いた方が自然に見える

最適化のために最大公約数を求める必要があって、
ユークリッド互除法と拡張ユークリッド互除法を書いたので、チラ裏に残しておく*1。

ユークリッド互除法

まずはよく見る実装をC#で

        public static int Gcd(int a, int b)
        {
            while (b != 0)
            {
                int r = a % b;
                a = b;
                b = r;
            }
            return a;
        }

実にありがちな実装なのですが、どう見てもダサすぎ。

これってつまり、こういうことだよね。

        public static int GcdR(int a, int b)
        {
            if (b == 0) return a;
            return GcdR(b, a % b);
        }

スッキリしました。

何を思ったか、久々にHaskellでも書いてみることに。
って、実はHaskellでは最初からgcd関数が定義されていたりする。
http://www.zvon.org/other/haskell/Outputprelude/gcd_f.html

なので

main :: IO()
main = return (gcd 1029 1071) >>= print

これで、21って答えが出ちゃったりする。

でも、自分で書いてみることに意味があるよね。たぶん。

gcd2 :: Int -> Int -> Int
gcd2 a 0 = a
gcd2 a b = gcd2 b (rem a b)

こんだけ。書くまでもなかった。

拡張ユークリッド互除法

よく見る実装をC#で。

        public static int GcdEx(int a, int b)
        {
            int x1 = 0;
            int x2 = 1;
            int y1 = 1;
            int y2 = 0;
            int r1 = b;
            int r2 = a;

            while (true)
            {
                if (r1 == 0) return r2;

                //Math.DivRemなんてのもあるけど
                int q = (int)Math.Floor((double)(r2 / r1));
                int r = r2 % r1;

                int x = x2 - q * x1;
                int y = y2 - q * y1;

                if (r == 0) break;

                x2 = x1;
                x1 = x;
                y2 = y1;
                y1 = y;
                r2 = r1;
                r1 = r;
            }
            return r1;
        }

うへ。これはひどい・・・。
なんというローカル変数の乱立ｗｗｗ

これも再帰で表現したほうがスッキリできそうです。
実際に書いてみると、こんな感じでした。

        private delegate TResult Func<T1, T2, T3, T4, T5, T6,TResult>(T1 a1, T2 a2, T3 a3, T4 a4, T5 a5, T6 a6);
        public static int GcdExR(int a, int b)
        {
            Func<int, int, int, int, int, int, int> f = null;
            f = (a2, b2, w2, x2, y2, z2) =>
            {
                if (b2 == 0) return a2;
                return f(b2, a2 % b2, x2, (w2 - a2) / b2 * x2, z2, (y2 - a2) / b2 * z2);
            };
            return f(a, b, 1, 0, 0, 1);
        }

いざ書いてみると、引数を６つとるFuncがないことに気付く…ｗ
一見わかりにくそうに見えるかもしれませんが、個人的には上に書いたよく見る実装よりも、
こちらの方が好みです。書き方的に「今風」っぽいというのも含めて。
あと、ラムダ式ばっか書いてると、匿名delegateでの旧式な書き方を忘れ気味であることに気付いた俺ガイル。

締めにHaskellでも

gcdex :: Int -> Int -> Int
gcdex a b = gcdex' a b 1 0 0 1
  where
    gcdex' a 0 _ _ _ _ = a
    gcdex' a b w x y z = gcdex' b r y z (w-y*q) (x-z*q)
      where (q, r) = quotRem a b

こうしてみると、やっぱHaskellはクールだなあ。

*1:負の数に関しては考えていません