Personal tools

99 questions/Solutions/32

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
 
Line 19: Line 19:
 
| otherwise = myGCD b (a `mod` b)
 
| otherwise = myGCD b (a `mod` b)
 
</haskell>
 
</haskell>
  +
  +
  +
[[Category:Programming exercise spoilers]]

Latest revision as of 19:42, 18 January 2014

(**) Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm.

gcd' 0 y = y
gcd' x y = gcd' (y `mod` x) x
myGCD x y | x < 0     = myGCD (-x) y
          | y < 0     = myGCD x (-y)
          | y < x     = gcd' y x
          | otherwise = gcd' x y

The Prelude includes a gcd function, so we have to choose another name for ours. The function gcd' is a straightforward implementation of Euler's algorithm, and myGCD is just a wrapper that makes sure the arguments are positive and in increasing order.

A more concise implementation is:

myGCD :: Integer -> Integer -> Integer
myGCD a b
      | b == 0     = abs a
      | otherwise  = myGCD b (a `mod` b)