Better Know an Algorithm

There are many algorithms known to computer science but far fewer known to your typical computer programmer. Descriptions of the algorithms are often hidden away in dense and dusty tomes seldom read today when information is typically so readily available just a web search away.

The problem is algorithms are difficult to search for when all you have is a raw problem statement to go on. Algorithms often have eponymous names which while useful for attribution and occasionally disambiguation are terrible for discovery.

I believe that the only way to effectively choose the right algorithm to solve a problem is to have a broad and general awareness of known algorithms such that a problem description may jog a bit of your memory and lead you back to an algorithm you’ve seen before. Many algorithms are also beautiful in the own right, painstakingly reduced until only the essential elements remain.

Thus in this series of post I want to introduce you to many algorithms from a variety of sources but first and foremost Knuth’s The Art of Computer Programming.

Algorithm E: Euclid’s Algorithm

The very first algorithm in TAOCP Volume 1 is Euclid’s algoirthm for finding the greatest common divisor of two positive integers. Knuth describes most of his algorithms using simple and precise natural language.

E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer. E3. [Reduce.] Set m ⟵ n, n ⟵ r, and go back to step E1. ❚