CODEWITHSUNDEEP
haskell
Dynamic
Dynamic

Reputation: 927

GCF/LCM in Haskell

I'm extremely new to Haskell.

Is there a simple way to find the GCF or LCM (Least Common Multiple) in Haskell?

Upvotes: 7

Views: 9212

Answers (4)

Thomas Gak-Deluen
Thomas Gak-Deluen

Reputation: 2971

Or you could also do

euclid(n,m) =
  if n == m then n
  else if n < m then euclid(n, m-n)
    else euclid(n-m, m)

Upvotes: 1

Erik Hinton
Erik Hinton

Reputation: 1946

I'm not sure what the LCF is but the GCF is a Haskell favorite. Using the Euclidean Algroithm you can really get a sense of how Haskell works. http://en.wikipedia.org/wiki/Euclidean_algorithm There is a great explanation of how the algorithm is set up here http://en.literateprograms.org/Euclidean_algorithm_(Haskell) .

This type of recursion is common in Haskell and it shows how expressive the language can be.

gcd a 0 = a
gcd a b = gcd b (a `mod` b)

This uses pattern matching on the arguments to say the greatest common factor of any number and 0 is the first number. If the numbers are both non-zero, then look for the greatest common factor of the second and the first mod the second. Eventually this will reach 0 in the second argument. This will trigger the first pattern and return the first argument which is the answer.

[EDIT]

The function should actually be: 

gcd a 0 = a
gcd a b = b `seq` gcd b (a `mod` b) where

This will force the evaluation of the previous recursion step's (a mod b) and will prevent a huge thunk being built in memory if, say, you are GCDing 1243235452 and 6095689787662. Seq forces the argument into its "Weak Head Normal Form" or evaluates the outer most data structure of the argument.

Upvotes: 8

Daniel Fischer
Daniel Fischer

Reputation: 183968

By GCF, do you mean the greatest common factor, or greatest common divisor? That's gcd, avaliable from the prelude, as is lcm, the least common multiple.

Upvotes: 16

Philip JF
Philip JF

Reputation: 28539

gcd is imported in the prelude. That means that you can use it whenever you want without going anything. Erik Hinton shows a simple version of the Euclidean algorithm, if you are interested in implementing your own. One thing though: / is used only for floating point division, use div and mod to find the quotient and remainder when you want to do "integer division." The prelude also defines a lcm function for least common multiple.

Upvotes: 4

Related Questions