I am using Euclid's algorithm for computing  GCD(M,N), the greatest common divisor of two integers M and N.

Though this code works well, I felt it's bit cumbersome to wrap it with max, min, and abs for both variables (a, b).

1. Can anyone suggest a better way to make the code less verbose?
2. I found the built-in gcd type was defined as gcd :: Integer a => a -> a -> a, but I cannot simply use it. What do I need to change in order to reuse the type definition?

gcd2 :: Int -> Int -> Int
gcd2 a b =
    let x = max (abs a) (abs b)
        y = min (abs a) (abs b)
        in if (y == 0) || (x == y && x > 0) 
           then x 
           else gcd2 y (x-y)

Well, inspired by chi, I changed the code as below.

gcd3 :: Int -> Int -> Int
gcd3 a b | a <  0 = gcd3 (-a) b
         | b <  0 = gcd3 a (-b)
         | b >  a = gcd3 b a
         | b == a || b == 0 = a
         | otherwise = gcd3 b (a-b)

This is the best I can do. :)

CodePudding user response：

You can look at how it is implemented in base:

gcd             :: (Integral a) => a -> a -> a
gcd x y         =  gcd' (abs x) (abs y)
                   where gcd' a 0  =  a
                         gcd' a b  =  gcd' b (a `rem` b)

CodePudding user response：

As suggested by chi in his answer, to avoid using abs in each recursive step I’d define a GCD local function where you pass the absolute value of the arguments. This way the implementation is pretty straightforward:

gcd :: Int -> Int -> Int
gcd a b = gcd' (abs a) (abs b)
  where gcd' a 0 = a
        gcd' a b = gcd' b (a `mod` b)