Prime Dijkstra

Recently, I heard something about Dijkstra's algorithm for finding primes. The details were hidden behind a Patreon, but I determined they referenced this article from 1976. That article is hidden behind an IEEE paywall, but it references E. W. Dijkstra, "Structured programming", 1969. I'm not certain, but I think that means EWD249.

Edsger W. Dijkstra (1930 - 2002) was a programmer back before there was such a thing. At least, officially. He was a "Programmer" at Mathematisch Centrum Amsterdam where he met "Calculator" Maria C. Debets. When they were married, he was legally required to state his profession. He said programmer, but that was rejected as there was then no such profession in The Netherlands.

Dijkstra did a number of things, but he is undoubtedly most famous for his shortest path algorithm. So much so that it is difficult to search on the internet for his prime-finding algorithm or indeed anything else that he did. As soon as you put Dijkstra, all the hits are for the shortest path algorithm. If you put "Dijkstra", virtually anything else, and "algorithm", you will probably not see anything other than shortest path things for the rest of the day.

He kept notes throughout his life called EWDs. I recently mentioned EWD35, which discusses semaphores, in a presentation I made to a book club.

EWD249 is not about finding prime numbers, per se, but it does use that as an example of how to do structured programming.

For fun, I went through that paper and rendered the prime-finding algorithm in Algol (Dijkstra also wrote the first Algol compiler).

PROC primes = (INT m)[]INT:
(
  [m]INT p;
  INT j := 1;
  INT k := 1;
  INT ord := 1;
  INT square := 4;
  p[1] := 2;

  WHILE k < m
  DO
     BOOL jprime := FALSE;
     WHILE NOT jprime
     DO
        j +:= 2;
        WHILE square <= j
        DO
           ord +:= 1;
           square := p[ord]**2
        OD;
        INT n := 2;
        jprime := TRUE;
        WHILE n < ord AND jprime
        DO
           INT r := j MOD p[n];
           jprime := (r /= 0);
           n +:= 1
        OD
     OD;
     k +:= 1;
     p[k] := j
  OD;

  p
);
 
print((primes(1000), new line))

All of the variable names are the same as in the paper except for the parameter m (he fixes it at 1000).

I installed an Algol compiler on my Debian machine with

❯ sudo apt install algol68g

which gave me the a68g command. I ran dijkstra-primes.a68 listed above with

❯ a68g dijkstra-primes.a68
                  +2                  +3                   ...                  +7919

The output is all on one line. I guess I need to pretty that up. That part is mentioned in the paper

The refinement of 2c “print p[k] for k from 1 through 1000” is left to the reader. I suggest that the table should be printed on five pages, each page containing four columns with fifty consecutive prime numbers.

but I don't think I care to learn enough Algol to do that. Maybe I should, though, because input/output is called transput in Algol! How cool is that?

The main routine is working, but I still need to polish the transput.

We need to bring this back!

Incidentally, there is an Algol mode for Emacs, so things needn't look so dreary as the above.

I don't think there's a language server for it though. 🙂