REVIEW - The Art of Computer Programming: Fundamental algorithms

Title:

The Art of Computer Programming: Fundamental algorithms

Author:

Donald Ervin Knuth

ISBN:

0201896834

Publisher:

Addison-Wesley Professional (1997)

Pages:

650pp

Reviewer:

Francis Glassborow

Reviewed:

June 1998

Rating:

★★★★★

While the material in these books is at a fundamental theoretical level no self-respecting programmer should be unaware of it. Some of it may be hard work but if more practitioners were familiar with Knuth's work we would have a better overall quality in our software.

I thought that I had reviewed the first of these some time last year when it came out but I can find no trace (I know I wrote something about it in EXE magazine). Anyway let me give newcomers an overview.

Back in the 1960's Donald Knuth started out to write a book in 12 chapters entitled 'The Art of Computer Programming' . By 1967 the plan had expanded to a seven-volume work (still only 12 chapters). The first three volumes had been published by 1973. Since then the first two volumes have been through 2nd editions and now 3rd editions. The outline for volume 4 (just two of the original 12 chapters) has expanded to three sub-volumes but we are still waiting to see it. The chance of volumes 6&7 ever being written seems increasingly remote.

Donald Knuth is one of the giants of programming. He has a vision of it that is almost beyond belief. Not only did he invent Literate Programming but wrote the software to make it possible. He then used those tools to create a definitive work (only five volumes) on computerised printing based on two major applications TEX and METAFONT. I could go on, but you get the picture.

I know of many reprints of books that contain more substantive changes than those between the second and third editions of The ACP v1. You probably think that programming constantly changes. The constancy and continued relevance of

Fundamental Algorithms is the other side. At a deep level very little has changed in thirty years.

In volume two there is more change, nothing major but just about enough to justify a new edition. Here we begin to see clues as to the root cause for the delays in the later volumes. This edition is almost a year late and the author marks some places as being work in progress. I guess that he has been constantly tempted to have one more final draft in order to get it absolutely up to date.

One of the interesting things I note in this volume is the heavily revised tables of coefficients for a couple of pseudo-random number generators. The basic algorithms are almost thirty years old but our hardware architecture has changed. Many of the original values work well with word sizes (36, 40 or 48 bit) that we no longer use. The dominance of 32-bit architectures (and 64-bit) means that different coefficients are needed. I wonder how many of you were aware of the influence of word size on the choice of coefficients for pseudo random number generators?

While the material in these books is at a fundamental theoretical level no self-respecting programmer should be unaware of it. Some of it may be hard work but if more practitioners were familiar with Knuth's work we would have a better over all quality in our software.


Book cover image courtesy of Open Library.