Greatest Common Divisors using LISP and Ruby

In the article TDD Beyond Basics : Greatest Common Divisor, we used iteration to implement Euclid's algorithm to compute GCD of two integers. In this article, we will see how to use a recursive procedure to implement Euclid's algorithm. I am learning LISP from the book Structure and Interpretation of Computer Programs by Gerald Jay Sussman and Hal Abelson. The solution will be in LISP and compare with the Ruby equivalent of the solution.

You should already know the concept of reduction and the discussion in the earlier article. Reduction is covered in one of the earlier articles, you can search for reduction to find them. The beauty of the LISP language is that the solution is only four lines of code as compared to almost 30 lines of code in my earlier article. Here are my notes from the book.

The greatest common divisor (GCD) of two integers a and b is defined to be the largest integer that divides both a and b with no remainder. For example, the GCD of 16 and 28 is 4. One way to find the GCD of two integers is to factor them and search for common factors. Another way that is much more efficient is Euclid's algorithm.

The idea of the algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus, we can use the equation:

GCD(a, b) = GCD(b, r)

to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example:

GCD(206, 40) = GCD(40, 6)
                        = GCD(6 , 4)
                        = GCD(4 , 2)
                        = GCD(2,  0)
                        = 2

reduces GCD(206, 40) to GCD(2, 0) which is 2. It is possible to show that starting with any two positive integers and performing repeated reductions will always eventually produce a pair where the second number is 0. Then the GCD is the other number in the pair. It is easy to express Euclid's algorithm as a procedure in LISP:

(define (gcd a b)
  (if (= b 0)
    a
  (gcd b remainder(a b))))

This generates an iterative process, whose number of steps grows as the logarithm of the numbers involved. In Ruby:

def gcd(a, b)
  if b == 0
    a
  else
    gcd(b, a % b)
  end
end

The remainder is a LISP builtin function that does the same thing as Ruby modulo operator %. Even though the procedure is recursive, this results in an iterative process because there is no pending operation used in the implementation.


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.