data tables

An important skill when implementing an algorithm is making sure your data variables hold the correct data. One way to do this, is to do so manually with a pen and paper, a whiteboard or an iPad.

What i'm trying to communicate is: the best way to make sure you understand what your algorithm is doing, is to do the number-crunching by hand, and to do so as neatly as you possibly can, by drawing tables of values.

If you're working with a pen, then create clean tables with rows and columns, and draw arrows and show your thinking and your work clearly.

If you're in an editor, then it takes a bit more skill at drawing ascii art, but it can absolutely be done. You're essentially using your editor as a drawing board.

Let's take a look at the greatest common divisor algorithm, with simple numbers: 20 and 30. Let's begin with the high-school method of listing all their divisors.

120              30
210 x 2          15 x 2
35  x 4          10 x 3
42  x 10         6  x 5
51  x 20         1  x 30

The tables above are typical of what you'd actually write out in your editor as a starting point.

Since we took the time to create this table meticulously, we can clearly see that 10 is the GCD of 20 and 30. Now the algorithm above doesn't seem very efficient; there is a better one.

A better GCD algorithm

Computing remainders is far more efficient. The solution goes like this:

• find the remainder r of a % b
• assign b to a, and r to b
• continue until b == 0
• the GCD is a

Now we could jump straight into code, however let's prove to ourselves that it works first:

 1a  % b  = r
 2------------
 320 % 30 = 20
 4     /    /
 5    /    /
 6   /    /
 7  /    /
 8 v    v
 930 % 20 = 10
10     /    /
11    /    /
12   /    /
13  /    /
14 v    v
1520 % 10 = 0

Implementation

We seem to have design an algorithm, so let's attempt to implement it.

1def GCD(a, b):
2  while b:
3      a, b = b, a % b
4  return a