The Art of Computer Programming exercise question: Chapter 1, Question 8

Question

I'm doing the exercises to TAOCP Volume 1 Edition 3 and have trouble understanding the syntax used in the answer to the following exercise.

Chapter 1 Exercise 8

Computing the greatest common divisor of positive integers m & n by specifying T_j,s_j,a_j,b_j

Let your input be represented by the string a^mbⁿ (m a's followed by n b's)

Answer:

Let A = {a,b,c}, N=5. The algorithm will terminate with the string a^gcd(m,n)

    j     Tj     sj    bj    aj
    0     ab  (empty)  1    2   Remove one a and one b, or go to 2.
    1   (empty)  c     0    0   Add c at extreme left, go back to 0.
    2     a      b     2    3   Change all a's to b's
    3     c      a     3    4   Change all c's to a's
    4     b      b     0    5   if b's remain, repeat

The part that I have trouble understanding is simply how to interpret this table. Also, when Knuth says this will terminate with the string a^gcd(m,n) -- why the superscript for gcd(m,n) ?

Thanks for any help!

Edited with more questions:

What is T_j -- note that T = Theta

What is s_j -- note that s = phi

How do you interpret columns b_j and a_j?

Why does Knuth switch a new notation in the solution to an example that he doesn't explain in the text? Just frustrating. Thanks!!!

Answer 1

The superscript for gcd(m,n) is due to how numbers are being represented in this table.

For example: m => a^m n => b^n

gcd(m,n) => a^gcd(m,n)

It looks to be like Euclids algorithm is being implemented. i.e.

gcd(m,n):
  if n==0:
    return m
  return gcd(n,m%n)

The numbers are represented as powers so as to be able to do the modulo operation m%n.

For example, 4 % 3, will be computed as follows: 4 'a's (a^4) mod 3 'b's (b^3), which will leave 1 'a' (a^1).

Answer 2

Here's an implementation of that exercise answer. Perhaps it helps.

By the way, the table seems to describe a Markov algorithm.

As far as I understand so far, you start with the first command set, j = 0. Replace any occurencies of T_j with s_j and jump to the next command line depending on if you replaced anything (in that case jump to b_j, if nothing has been replaced, jump to a_j).

EDIT: New answers:

A = {a,b,c} seems to be the character set you can operate with. c comes in during the algorithm (added to the left and later replaced by a's again).

Theta and phi could be some greek character you usually use for something like "original" and "replacement", although I wouldn't know they are.

b_j and a_j are the table lines to be next executed. This matches with the human-readable descriptions in the last column.

The only thing I can't answer is why Knuth uses this notation without any explanations. I browsed the first chapters and the solutions in the book again and he doesn't mention it anywhere.

EDIT2: Example for gdc(2,2) = 2

    Input string: aabb
    Line 0: Remove one a and one b, or go to 2.
    => ab => go to 1
    Line 1: Add c at extreme left, go back to 0.
    => cab => go to 0
    Line 0: Remove one a and one b, or go to 2.
    => c => go to 1
    Line 1: Add c at extreme left, go back to 0.
    => cc => go to 0
    Line 0: Remove one a and one b, or go to 2.
    No ab found, so go to 2
    Line 2: Change all a's to b's
    No a's found, so go to 3
    Line 3: Change all c's to a's
    => aa
    Line 4: if b's remain, repeat
    No b's found, so go to 5 (end).

    => Answer is "aa" => gdc(2,2) = 2

By the way, I think description to line 1 should be "Remove one "ab", or go to 2." This makes things a bit clearer.

Answer 3

the notion of a^m is probably a notion of input string in the state machine context.

Such notion is used to refer to m instances of consecutive a, i.e.:

a⁴ = aaaa
b⁷ = bbbbbbb
a⁴b⁷a³ = aaaabbbbbbbaaa

And what a^gcd(m,n) means is that after running the (solution) state machine, the resulting string should be gcd(m,n) instances of a

In other words, the number of a's in the result should be equal to the result of gcd(m,n)

And I agree with @schnaader in that it's probably a table describing Markov algorithm usages.