MMIX Supplement to The Art of Computer Programming, Section 1.3.3, Program A

Content

Bug fix for Program 1.3.3A

Report

Reported May 17, 2015, by Alexander J. Conley.

Description

Program A, as published, will advance in line 33 to the character following an opening parenthesis and loads it into start without checking whether it is a formatting character. As a consequence, formatting characters that follow immediately after an opening parenthesis will be treated as symbols.

Test Case

File proga.5.in

(ACF G) ( BCD)
(AED) (FA DE) ( BGFAE)

will produce

(ADBCE G)

correct is

(ADG)(CEB)

Discussion

There are several ways to fix this bug.

The code of lines 26 to 28 could be repeated after line 34. This would add the necessary test, replace any formatting character by a zero byte, and skip it.
The resulting code would be closest to Knuths original solution. On the other hand, the code would duplicate three lines of code. This would make the code longer and invalidate all references to line numbers in the following text.
The code in lines 33 to 35 could be replaced by the single line
```
  SET start,0
```
and after line 28 the line
```
  CSZ start,start,current
```
could be inserted.
This would initialize the value of start with zero as soon as an opening parenthesis occurs in the input. The value zero in start would then be replaced by the first nonzero character (that is nonformatting character) that occurs after the opening parenthesis due to the line inserted.
The resulting code would be one line shorter and slightly less efficient than the previous solution because the more general loop will test not only for formatting characters but also for an opening or closing parenthesis, which in a correct input will never follow after the opening parenthesis.
The different control flow requires changes in the analysis of the algorithm that follows in the text.
The code in lines 33 to 35 could be replaced by
```
  SET start,0
  JMP 0F
```
and after line 28 the line
```
  CSZ start,start,current
```
could be inserted.
The only difference to the previous solution is skipping the test for a closing parenthesis just after the opening parenthesis saving two cycles for each opening parenthesis. Further, the resulting code has the same length as before, so most line references in the text would remain valid.

The first solution duplicates code but retains the efficiency of Knuths original algorithm. If we assume that formatting characters that follow after an opening parenthesis are rare, the loss in efficiency incurred by the last solution is compensated by the simpler code.

Link to Old Program

Link to New Program

Changes to the MMIX Supplement

page 2:
After line 28 insert
```
  CSZ start,start,current
```
Replace lines 33 to 35 by
```
  SET start,0
  JMP 0F
```
The line numbers between line 29 and line 35 change accordingly. No line numbers need to change before line 29 and after line 35.
In line 36 and line 37, replace the instruction count "C" by "A-B".
page 3:
In the second line preceding equation (7), delete "and the branch in line 35 is never executed".
In equation (7), replace "6A + 7B + 4C" by "9A + 4B + 2C"
page 4:
Replace the second line in the table by
```
35,37,39,40   C = B + (A - B - D) + D
```
In the line preceding equation (9), delete ", 33,".
In equation (9), delete "B + ".
In the line preceding equation (10), replace "31" by "32".
In the line preceding equation (14), replace "32" by "33".
page 5::
In the second line preceding equation (17), delete "B + ".
In equation (17), replace "(B + C)" by "C".
Replace equation (18) by "(6NX+17X+4M+2Y+8U+7N+7)υ".
page 120::
In the second line of Solution 7, replace "2095" by "2164".
In the third line of Solution 7, delete ", V=1" and replace "1805" by "1869".

Please help to keep this site up to date! If you want to point out important material or projects that are not listed here, if you find errors or want to suggest improvements, please send email to