[Solved] Implementing Extended Euclidean algorithm

by


I think you might be looking for something like this:

combine :: Int ->Int -> (Int,Int,Int)
combine n m = (x1, y1, gcd n m) where
  (x1, y1) = gcdext n m

gcdext :: Int -> Int -> (Int, Int)
gcdext n m = gcdexthelper n m 1 0 0 1 where
  gcdexthelper n m x1 y1 x2 y2 
   | m == 0 = (x1, y1)
   | otherwise = gcdexthelper m r x1p y1p x2p y2p where
     q = div n m
     r = mod n m
     x1p = x2
     y1p = y2
     x2p = x1 - q * x2
     y2p = y1 - q * y2

You can of course implement the same with a while loop, but I believe recursion is much more readable in Haskell, so I used it here.

And by the way, GCD is a standard library function in Haskell, so no need to write your own.

2

solved Implementing Extended Euclidean algorithm