AoCP | BASIC CONCEPTS

The Art of Computer Programming was recently brought to my attention as something to check out. I figured it was another fairly technical text covering a few design patterns, describing object orientation, variable types, when to use certain languages, and other related programming topics. I could not have been more incorrect. After only reading the Preface and part of the BASIC CONCEPTS section, I can tell this is something totally different. Reading further about the author, Donald Knuth, its obvious why the book has this vibe of incredible detail and pure understanding. At first, I thought the text was going to be inaccessible because I spotted a few crazy formulas. I was reassured that there is a method to the madness; an actual guide on *how* to read the book. Donald makes it clear that he understands certain areas of math arent for everyone and provides a way to still get through the book material without becoming overwhelmed.

We start this journey with algorithms. They are strategies for solving a particular problem, a framework for approaching a question. The example used in BASIC CONCEPTS is Euclid’s greatest common divisor algorithm, E. Essentially, the two starting numbers are divided, leaving a remainder. This remaining chunk must be dealt with by forcing it to approach 0. The best way to approach zero algorithmically is to ensure that it always reduces in size each iteration. This is accomplished in E3, since both numbers are guaranteed to be less than the previous iteration. Simple and effective, but not necessarily intuitive.

Given two positive integers m and n, find the greatest common divisor.
E1. [Find remainder] Divide m by n and let r be the remainder. 0 <= r <= n now holds.
E2. [Is it zero?] If r is 0, terminate since n is the answer.
E3. [Reduce] Set m = n and n = r, then repeat from E1.

Lets implement this in Python3 and watch it work. One of my favorite aspects of computer science is the ability to watch a system in action after considering it, even with very simple examples like this. Its also worth noting that Euclid GCD falls into the category of a divide-and-conquer algorithm, since it uses the loop output to reduce the size of the problem set during the next loop.

#!/usr/bin/python3

def euclid_gcd(m, n):
    while True:
        r = m % n
        print('m is {}, n is {}, remainder is {}'.format(m,n,r))
        assert(0 <= r <= n)
        if r == 0:
            return n
        else:
            print('setting m({}) to n({})'.format(m, n))
            m = n
            print('setting n({}) to remainder({})'.format(n, r))
            n = r

def main():
    m = 100
    n = 30
    print('GCD of {} and {} is {}'.format(m, n, euclid_gcd(m, n)))

if __name__ == '__main__':
    main()
~/aocp/basic_concepts$ ./euclid.py 
m is 100, n is 30, remainder is 10
setting m(100) to n(30)
setting n(30) to remainder(10)
m is 30, n is 10, remainder is 0
GCD of 100 and 30 is 10

Knuth details several characteristics that an algorithm must have. First, it must be finite in time. It must be guaranteed to give a result after a defined amount of steps, even if that number of steps is "arbitrarily large." A way to guarantee finiteness is to ensure that during each loop, the condition the algorithm works towards is being approached in some meaningful way. He gives an interesting insight about non-terminating methods, they cannot be algorithms. For example, a *reactive process* which doesn't handle its internal state entirely; its affected by the outside environment and cannot therefore be guaranteed to terminate. Second, an algorithm must be definite. Each step has to be discrete and no unknown state can occur. In the Euclid example above, the algorithm is guaranteed to be definite because the inputs are restricted to positive integers. If m and n were instead negative or imaginary numbers, the remainder may not be computable in a way that the algorithm can handle. Therefore, the space must be restricted to maintain definiteness. Third, an algorithm must have zero or more inputs. The same holds for outputs. Lastly, an algorithm should be effective. This sounds quite general at first, but Knuth means that it should be fast and simple. In his words, "...in the sense that its operations must be sufficiently basic that they can in principle be done exactly and in a finite length of time by someone using a pencil and paper." He compares algorithms to a proper recipe; you don't want to add "a pinch" of salt, rather the recipe should specify exactly how much salt based on the inputs, like size of the roast. The general measure for an algorithms "goodness" is its speed, which comes from simplicity. The balance of simple atomic steps to solve a complex problem is the challenge presented to someone designing an algorithm.

He presents an exercise to find the greatest common divisor of 2166 and 6099, which is 57. Its interesting to watch the algorithm work when switching m and n then reaching the same result, converging on the same computations. When the smaller number is divided by the larger number, the remainder is the entire smaller number of course. Then the algorithm does its assignments and the values are swapped.

~/aocp/basic_concepts$ ./euclid.py 
m is 2166, n is 6099, remainder is 2166
setting m(2166) to n(6099)
setting n(6099) to remainder(2166)
m is 6099, n is 2166, remainder is 1767
setting m(6099) to n(2166)
setting n(2166) to remainder(1767)
m is 2166, n is 1767, remainder is 399
setting m(2166) to n(1767)
setting n(1767) to remainder(399)
m is 1767, n is 399, remainder is 171
setting m(1767) to n(399)
setting n(399) to remainder(171)
m is 399, n is 171, remainder is 57
setting m(399) to n(171)
setting n(171) to remainder(57)
m is 171, n is 57, remainder is 0
GCD of 2166 and 6099 is 57

~/aocp/basic_concepts$ ./euclid.py 
m is 6099, n is 2166, remainder is 1767
setting m(6099) to n(2166)
setting n(2166) to remainder(1767)
m is 2166, n is 1767, remainder is 399
setting m(2166) to n(1767)
setting n(1767) to remainder(399)
m is 1767, n is 399, remainder is 171
setting m(1767) to n(399)
setting n(399) to remainder(171)
m is 399, n is 171, remainder is 57
setting m(399) to n(171)
setting n(171) to remainder(57)
m is 171, n is 57, remainder is 0
GCD of 6099 and 2166 is 57

Leave a Reply