Articles Feed

Ruby and the Art of Computer Programming

by: paul | November 6th, 2007 |

Recently, I started to read the Knuth’s Art of Computer Science. To spice up the exercises, I am writing them out in ruby. Thinking about the basic math of programming and how to implement it in a high level language like ruby has been fun. The evolution of programming languages has gone far since the book was written. We can use cool new ruby syntax to do multiple steps in an algorithm!

Also, this is an exercise in writing clean code. Some of the algorithms in the book are a bit hard to read in there pure math form. So, when I write them out in ruby, I try to use as much expressiveness without adding clutter. This is no easy task, and often times I have to walk away from an algorithm for awhile and come back to it, because I will have my head deep in the math and less in the code. Or vice versa.

I was showing one of my solutions to a colleague of mine, Doug Bradbury, who saw a better way in ruby to solve the same problem I was with less lines of code and a higher readability. So, I decided to share one of the problems, and in a few days, I will post my version of the solution. We can see different solutions in different languages and different styles. Go ahead and try it out.

Here is the algorithm as written in the book.

This is Euclid’s Algorithm for the greatest common divisor

E0 [Ensure m >= n.] If m < n, exchange m <--> n.
E1 [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 <= r < n.)
E2 [Is it zero?] If r = 0, the algorithm terminates;n is the answer.
E3 [Reduce.] Set m <- n><- r>


UPDATE: Here is a solution

def are_whole_numbers?(*numbers)
  numbers.each {|number| return false if number.to_i.to_f != number}
  return true
end

def euclid(m, n)
  raise "Must be whole numbers." unless are_whole_numbers?(m, n)
  return euclid(n, m) if m < n

  remainder = m % n

  return n if remainder == 0
  return euclid(n, remainder)
end

#Here are some examples
puts euclid(35.0, 40.0) #should be 17.0
puts euclid(119.0, 544.0) #should be 17.0
puts euclid(555.0, 666.0) #should be 111.0

2 Responses to “Ruby and the Art of Computer Programming”

1. Eric Peterson Says:
   October 18th, 2008 at 06:32 PM The first example should be 5, fwiw. Also, a solution in ocaml with some unnecessary parentheses added for clarity, just in case you've never seen ocaml before:

   let rec euclid m n =
       if m < n then (euclid n m) else
       match (m mod n) with
       |0 -> n
       |r -> euclid n r

2. Paul Pagel Says:
   October 18th, 2008 at 06:32 PM Right you are!!! Good catch

Leave a Reply

Name (required)

Mail (will not be published)

Website

#