# Recent News

## 1000000 Years Old!

I got a bit older at the beginning of this year ... and, wow, what a wonderful surprise celebration we had! I can't sufficiently thank all my friends who traveled to Stanford and treated me to some of the absolutely most thrilling days of my life, as we celebrated the joys of Computer Science in general and Analysis of Algorithms in particular. Great talks by Persi Diaconis, Scott Kim, Bob Sedgewick, Philippe Flajolet, Svante Janson, Jeff Vitter, Andrei Broder, Andrew Odlyzko, Herb Wilf, Bob Tarjan, Leo Guibas, and Vaughan Pratt --- plus a great organ concert by Gwen Adams and Joseph Hansen --- and a chance to greet more than a hundred people that I rarely get to see, including more than twenty of the students whose dissertations I've had the good fortune to sign in years past. Thank you all enormously for a festive event that will live forever in my memory. It could not have been more perfect!

## Farewell, Mom

Everyone who came to my birthday party was able to meet my indefatigable mother, Lou, who was still continuing to work with real estate in downtown Milwaukee long after I myself had retired. Alas, her age finally caught up with her, and she passed away at the end of June. (When she died she was exactly 32,758 days old, just ten short of \$2^{15}\$.) She was, thankfully, able to put her life in order and to have many upbeat moments with family and friends during the final months. Here is a memorial booklet that celebrates her life and work.

## A Better Random Number Generator

The third edition of Seminumerical Algorithms introduced a nice, portable random number generator called ran_array --- or, in FORTRAN, RNARRY. To use this generator, people call "ran_start(seed)" --- or RNSTRT(SEED), a la FORTRAN.

Late last year I received a message from a researcher in Spain, Pedro Gimeno, who noticed a new type of deficiency in this generator. He was using ran_array to generate only a few random numbers, but he was initializing it with many different seed values. This mode of usage had never been considered before in the literature, as far as either of us knew, and he found that essentially every generator he tried was giving him problems when used in such a way.

Indeed, I had never tried testing a random number generator by looking only at the first few numbers that correspond to seeds 1, 2, ..., 1000000 (say). So I tested ran_array/ran_start in Gimeno's manner; lo and behold, several tests for randomness failed.

I couldn't figure out why such a problem could occur, because both ran_array and ran_start have fairly substantial theoretical underpinnings; so I asked Richard Brent for help. Working with Gimeno, he carried out elaborate tests and found two cures for the problem: (1) Discard the first 2000 numbers produced by ran_array after it has been started. (2) Improve the algorithm used by ran_start to prime the pump. With either (1) or (2), no statistical bias is detected in the resulting numbers by Marsaglia's famous "Die Hard" battery of tests.

Brent and Gimeno recommended using BOTH fixes (1) and (2), to be doubly confident that residual nonrandomness isn't lurking.

So I've done that. The new method appears in the ninth printing of Seminumerical Algorithms (January 2002), and sources in both C and FORTRAN are freely available. Fortunately the new version is shorter and easier to understand than the original.

Please note, however, that the new version is NOT compatible with the old. The procedure ran_array has not changed, but the seed-value initialization by ran_start is quite different, so you get different results.

As before, the programs have been carefully written so that identical results are obtained with both C and FORTRAN routines, in both the integer version and the double-precision floating point version. The method can also be ported readily to other languages.

## New super-improved CWEB sources

Hip, hip, hooray, a long-cherished dream is now a reality: CWEB version 3.6 introduced new features for clickable hypertext links by which you can read programs with Acrobat. It also contained extensive revisions that greatly improve its support for C++. And version 3.64 (March 2, 2002) is even better! See my CWEB page for full details.

I strongly urge all CWEB users to upgrade to version 3.64 as soon as possible. Version 3.6 represented the first nontrivial change to that system in many years --- although I decided not to call it version 4 --- and version 3.61 extended it to hypertext. Version 3.64 corrects and improves several aspects of those early releases. My present intention is that version 3.64 will in fact be the very last upgrade (except of course for fixes to catastrophic bugs).

## Stanford GraphBase Update

A glorious new printing of The Stanford GraphBase is now available from the publishers, with corrections to all known errors. More than half of the pages of the previous printing have been improved; and I've added a few new jokes too.

## Previews of Volume 4

I've been making some headway at last on actually writing Volume 4 of The Art of Computer Programming instead of merely preparing to write it, and some first drafts are now ready for beta-testing. I've put them online primarily so that experts in the field can help me check the results, but brave souls who aren't afraid to look at relatively raw copy are welcome to look too. (Yes, the usual rewards apply if you find any mistakes.)

(Truly hardy adventurers may also wish to hunt for a sneak preview of the next few pages.)

• 7.2.1.1--96 (analysis of a coroutine-based algorithm)
• 7.2.1.1--98 (decoding a recursively generated de Bruijn cycle)
• 7.2.1.2--6 (analysis of lexicographic permutation generation for multisets)
• 7.2.1.2--7 (asymptotics of multiset permutation generation)
• 7.2.1.2--41 (Heap's method generalized to r-variations)
• 7.2.1.2--43 (a Sims table with only short cycles)
• 7.2.1.2--75 (enumeration of northeasterly knight's tours)
• 7.2.1.3--25 (proof of van Zanten's theorem)
• 7.2.1.3--32 (enumeration of genlex listings for bit strings)
• 7.2.1.3--33 (enumeration of genlex listings for index lists)
• 7.2.1.3--42 (analysis of an algorithm for near-perfect combination generation)
• 7.2.1.3--62 (minimal-change algorithm for contingency tables)
• 7.2.1.3--82 (properties of the amazing Takagi function)
• 7.2.1.3--92 (synchronized standard sets in toruses)
• 7.2.1.3--93 (counterexample when hypotheses are violated)
• 7.2.1.3--100 (the heaviest multicomplexes)
• 7.2.1.3--109 (universal cycles of 3-combinations with repetitions)

Note that you don't have to work the exercise first; you're allowed and even encouraged to peek at the answer. Please send success reports to the usual address for bug reports (taocp@cs.stanford.edu), if you have time to provide this extra help. Thanks in advance!

During a recent visit to Norway I was able to complete tracing my ``academic genealogy,'' namely to learn the names of my thesis advisor's advisor's advisor's ... advisor, as far back as I'll ever be able to go:

• Donald Ervin Knuth, 1938--, was a student of
• Marshall Hall, Jr., 1910--1990, who was a student of
• Øystein Ore, 1899--1968, who was a student of
• Thoralf Albert Skolem, 1887--1963, who was a student of
• Axel Thue, 1863--1922, who was a student of
• Elling Bolt Holst, 1849--1915, who was a student of
• Marius Sophus Lie, 1842--1899, who was a student of
• Carl Anton Bjerknes, 1825--1903, who was a student of
• Bernt Michael Holmboe, 1795--1850, who was a student of
• Søren Rasmussen, 1768--1850, who was self-taught.

## Homage to Ole-Johan

My dear friend Ole-Johan Dahl passed away this year --- during the same week as my mother, in fact --- and while I was in Norway I received from Knut Holmqvist a wonderful memento: excerpts from the time Dahl and I played a four-hands-piano arrangement of Gershwin's Rhapsody in Blue, on the day when the University of Oslo's new Institute for Informatics building was dedicated (19 September 1988). Here are those clips, as a QuickTime movie (5MB gzipped).

## Public lectures

Although I must stay home most of the time and work on books that I've promised to complete, I do occasionally get into speaking mode. Here is a current schedule of events that have been planned for this year so far:

20 March, 9am
keynote speech, "Bob Floyd, in Memoriam", at the annual meeting of the Stanford Computer Forum
Saturday, 30 March, 10:00am
speaking about "Combinatorial problems related to The Art of Computer Programming" at the Fourth BADMath Day, in room 380C of Stanford's mathematics department
Easter Sunday, 31 March, 11:00am
Playing the continuo organ at First Lutheran Church of Palo Alto, in a performance of Handel's Dettingen Te Deum [the service is actually being held at St Anne's, Melville Road and Tasso, while our church is being refurbished in preparation for a new pipe organ]
Thursday 11 April, 6pm
speaking about "Mathematical Typography" as part of the MSRI Museion Lecture Series
Friday 12 April, 7:30pm
discussing Things a Computer Scientist Rarely Talks About at College Heights UCC Church in San Mateo
Tuesday 23 April, at 4:30pm in Gates room B01
A Computer Musing lecture entitled ``Topological sorting revisited''
Friday, 30 August, 4:30pm in the Store Auditorium
``All questions answered'' as part of the 25-year jubilee celebration of the Informatics Institute at the University of Oslo; Quicktime video
Monday, 2 September, 11:00am
receiving a doctor's degree as part of the Abel Bicentennial in Oslo
Tuesday 3 September, 2:15pm in the Lille Auditorium at IFI
a lecture entitled ``Deconstructing Coroutines''
Tuesday 10 September, Oxford University Com Lab, 4:30pm
a lecture entitled ``Deconstructing Coroutines''
Tuesday 3 December, at 4:15pm in Stanford's SEQ teaching center, room 200
A Computer Musing lecture entitled ``Chains of subsets, and their curious relation to binary trees'' (the ninth annual Christmas tree lecture)
Tuesday 24 December, at 10:30pm
Playing the continuo organ at First Lutheran Church of Palo Alto, in a performance of Charpentier's Messe de Minuit pour Noël

Click here for the ``recent news'' that was current at the end of 2001, if you're interested in old news as well as new news.