My colleague Steve O’Grady recently posted a link to the blog post Math For Programmers by Steve Yegge.
While thinking of a forthcoming blog earlier today I realized I could make use of “binary search,” itself an application of mathematics to programming, in a forthcoming post, and so planned to use that as the first post in an occasional series on this topic.
However, my previous post discussed the generation of random numbers, and so constitutes the first such occasional post.
Generating a list of “random” numbers is itself a very difficult problem. Don Knuth devotes 170 pages to this topic in Vol. II of his masterpiece multi-volume series “The Art of Programming.” These are the best books so far written about programming and mathematics and I doubt they will ever be equalled.
As it happens I had the good fortune to have Professor Knuth as my instructor in a course in Group Theory while a sophomore at Caltech, before he became a professor at Stanford. Indeed I recall a later lecture or talk when he announced he would be leaving Caltech to go to Stanford.
I also had him as a customer, as I served him many a meal in my days as a waiter at the Caltech Athaneum. He was one of the few people who regularly ate there on the weekends.
But my first and most vivid memory of him is of a light burning in a window.
The Caltech campus was quite small back in the 1960’s when I went there. Moreover, it was located in the middle of a residential neighborhood so there wasn’t much to do. As a result I spent a great deal of time walking around the campus.
When I did so late at night I almost always saw that the lights were on in one of the offices in the Sloan building, home of the Mathematics department. I was curious to see who was working so late so often so I wandered by one time and saw that the name on the door was “Knuth.” This was when I was a freshman, before I had him as a professor.
A few years later, when Vol. I of his masterpiece appeared, I knew what he had been working on.
Knuth never finished the series of books he planned, though he continues to work on them in his retirement.
He got sidetracked because of problems getting Vol II properly typeset. As a result he decided to write on his own software that would support the proper display of mathematical papers. In one of the great feats of programming he developed software not only to format such text, but even to format the characters and symbols that comprise the text.
The end result was an open-source program called Tex. It has been available for over two decades and today is used to format almost all the mathematics and scientific papers in the world.
Most notable is that it was all done by Knuth himself. It is freely available under the following license:
The files in this directory are master files maintained personally by
Donald E. Knuth. Nobody else is authorized to make any changes whatever
to them! If you modify the files for any purpose, you must give your
files a different name, so that installations of TeX throughout the world
will be 100% compatible when they use the official source files.
Please help preserve the integrity of TeX by reporting any violations of
these rules to the TeX User Group.
What is particularly striking is the remarkable stability of the code. There are few if any known bugs. Knuth has offered for a number of years a small payment to anyone who finds an error in his work. He’s had to write only a few such checks, and almost none have been cashed because to receive one is a high honor indeed. The value to the recipient of such a check comes not from the cashing it but from being able to post it on their wall.
There is a parallel to this in the past. I recall reading in that wonderful series of books, “The World of Mathematics,” that Gauss was notable in that not a single error had ever been found in his published papers.