Printing Primes: An example of noweb

Printing Primes: An example of noweb

The following program is essentially the program that appears in Reference [cite knuth:literate], the first article on literate programming, but rendered using noweb. An important differents is the WEB has macros, but noweb does not. Knuth's program is itself essentially the same as Edsger Dijkstra's ``first example of step-wise program composition.'' [cite dahl:structured, pages 26--39].

Dijkstra's program prints a table of the first thousand prime numbers. We shall begin as he did, by reducing the entire program to its top-level description. 

<*>=
<program to print the first thousand prime numbers>

[[Double brackets will be used in what follows to enclose comments relating to noweb itself. This definition of the root module could have been eliminated by choosing to use

notangle -R'program to print the first thousand prime numbers'
to extract the program.]]

This program has no input, because we want to keep it simple. The result of the program will be to produce a list of the first thousand prime numbers, and this list will appear on the output file.

Since there is no input, we declare the value m = 1000 as a compile-time constant. The program itself is capable of generating the first m prime numbers for any positive m, as long as the computer's finite limitations are not exceeded. 

<program to print the first thousand prime numbers>= (<-U)
program print_primes(output);
  const m = 1000;
        <other constants of the program>
  var <variables of the program>
    begin <print the first m prime numbers>
    end.
Defines print_primes (links are to index).

Plan of the program

We shall proceed to fill out the rest of the program by making whatever decisions seem easiest at each step; the idea will be to strive for simplicity first and efficiency later, in order to see where this leads us. The final program may not be optimum, but we want it to be reliable, well motivated, and reasonably fast.

Let us decide at this point to maintain a table that includes all of the prime numebrs that will be generated, and to sepaerate the genreation problem from the printing problem. 

<print the first m prime numbers>= (<-U)
<fill table p with the first m prime numbers>;
<print table p>

How should table p be represented? Two possibilities suggest themselves: We could construct a sifficiently large aray of boolean values in whith the kth entry is true if and only if the number k is prime; or we could build an array of integers in which the kth entry is the kth prime number. Let us choose the latter alternatice, by introducing an intereger array called p[1..m]. In the documentation below, the notation p[k] will refer to the kth element of the array p, while p_k will refer to the kth prime number. If the program is correct p[k] will equal p_k or it will not yet have nbeen asigned any value. 

<variables of the program>= (<-U) [D->]
p: array [1..m] of integer; 
      { the first m prime numbers, in increasing order }

The output phase

<other constants of the program>= (<-U) [D->]
rr = 50;
cc = 4;
ww = 10;

<variables of the program>+= (<-U) [<-D->]
page_number: integer;
page_offset: integer;
row_offset: integer;
c: 0..cc;
Defines page_number, page_offset, row_offset (links are to index).

<print table p>= (<-U)
begin page_number := 1; page_offset := 1;
while page_offset <= m do
  begin <output a page of answers>;
  page_number := page_number + 1;
  page_offset := page_poffset + rr * cc;
  end;
end

<output a page of answers>= (<-U)
begin write('The First ');
write(m:1);
write(' Prime Numbers --- Page ');
write(page_number:1); write_ln; write_ln;
  { there's a blank line after the heading }
for row_offset := pages_offset to page_offset + rr - 1 
      do <output a line of answers>;
page;
end

<output a line of answers>= (<-U)
begin for c := 0 to cc - 1 do
  if for_offset + c * rr <= m then
    write(p[row_offset + c * rr]);
writeln;
end

Generating the primes

<fill table p with the first m prime numbers>= (<-U)
<initialize the data structures>
while k < m do
  begin <increase j until it is the next prime number>
  k := k + 1; p[k] := j;
  end

<variables of the program>+= (<-U) [<-D->]
j: integer;  { all primes <= j are in table p }
k: 0..m;     { this many primes are in table p }

<increase j until it is the next prime number>= (<-U)
repeat j := j + 2;
  <update variables that depend on j>;
  <give to j_prime the meaning: j is a prime number>
until j_prime

<variables of the program>+= (<-U) [<-D->]
j_prime: boolean;
Defines j_prime (links are to index).

<initialize the data structures>= (<-U) [D->]
j := 1; k := 1; p[1] := 2;

<variables of the program>+= (<-U) [<-D->]
ord: 2..ord_max;
  { the smallest index >= 2 such that p_ord squared > j }
square: integer;
  { square = p_ord squared }
Defines ord, square (links are to index).

<initialize the data structures>+= (<-U) [<-D]
ord := 2; square := 9;

<other constants of the program>+= (<-U) [<-D]
ord_max = 30;  { p_ord_max squared must exceed p_m }

<update variables that depend on j>= (<-U)
if j = square then
  begin ord := ord + 1;
  <update variables that depend on ord>
  end

<update variables that depend on ord>= (<-U) [D->]
square := p[ord] * p[ord];  { at this point ord <= k }

The inner loop

<give to j_prime the meaning: j is a prime number>= (<-U)
n := 2; j_prime := true;
while (n < ord) and j_prime do
  begin <if p[n] is a factor of j, set j_prime := false>;
  n := n + 1;
  end

<variables of the program>+= (<-U) [<-D->]
n: 2..ord_max; { runs from 2 to ord when testing divisibility }

<variables of the program>+= (<-U) [<-D]
mult: array [2..ord_max] of integer;
  { runs through multiples of primes }
Defines mult (links are to index).

<update variables that depend on ord>+= (<-U) [<-D]
mult[ord-1] := j;

<if p[n] is a factor of j, set j_prime := false>= (<-U)
while mult[n] < j do
  mult[n] := mult[n] + p[n] + p[n];
if mult[n] = j then j_prime := false;

Index

Chunks

Identifiers

References

[1] Donald E. Knuth. Literate programming. The Computer Journal, 27(2):97--111, 1984.

[2] Ole-Johan Dahl, Edsger W. Dijkstra, and C. A. R. Hoare. Structured Programming. Academic Press, London and New York, 1972.