Culture / Technology

Donald Knuth’s 2019 ‘Christmas Tree Lecture’ Explores Pi in ‘The Art of Computer Programming’

25 Dec 2019 6:00am, by

Donald Knuth 2019 - screenshot from Christmas Tree Lecture - Pi and the art of Computer Programming

For a quarter of a century, Stanford’s great computer science professor emeritus has been delivering a special “Christmas Tree” lecture each December. Now approaching his 82nd birthday, Donald Knuth emerged again on Dec. 5 for the 25th annual installment — and took the time to remind his audience that he’s also still diligently writing the book he’s been working on for the last 57 years.

That book is The Art of Computer Programming, revered among programmers as one of the most comprehensive analyses of algorithms available. The book is “widely considered to be among the best scientific writings of the century,” according to one web page at Stanford. “My full-time writing schedule means that I have to be pretty much a hermit,” writes Knuth on his personal site.

So it’s a doubly special occasion when the great man makes a live appearance.

And here at The New Stack, we have our own Christmas tradition: taking a good look — and sharing a few screenshots — from Knuth’s latest lecture. In 2017 I’d described it as “like visiting a favorite relative over the holidays” and “a chance to see a great mind in action.”

And this year’s lecture was no exception.

As Easy as Pi

Knuth’s lecture was given on Dec. 5, but only posted on Saturday, Dec. 21. (By Monday, it had already racked up over 2,000 views.)

Knuth had another reason to be proud, closing the lecture by holding up his copy of the just-published addition to The Art of Computer Programming. He described it as “the book that I think is tons of fun, and it also, by the way, teaches a few algorithms on the side.”

The Art of Computer Programming by Donald Knuth - cover of Volume 4, Fascicle 5

Volume 4, Fascicle 5 was released last month.

It looks like Knuth himself was having a lot of fun. “Thank you all for coming,” Knuth tells the audience. “I guess you haven’t gotten tired of me yet,” he jokes, adding “But we’ll see if anybody shows up next year…”

But for this year’s lecture, Knuth did something special. He showed the audience how, throughout the last half of a century, he’s whimsically worked the digits of pi into various exercises in his book — again, and again, and again. Knuth tells the audience that he’s searched the entire text of his own book, The Art of Computer Programming, using the Linux tool egrep, and he’s found a whopping 1,700 occurrences of the word pi, “which mean pi occurs maybe twice every five pages in the book so far.” He feels that using pi in his examples assures readers that the algorithms really will work, even on an arbitrarily chosen cluster of digits.

But before long his talk had turned into a kind of intellectual funhouse, sharing other pi-related miscellanies that are often surprising — and occasionally even mind-boggling.

He begins by showing the cover of the book The Numerology of Dr. Matrix by mathematician Martin Gardner and shares its diagram of the first 32 decimals of pi. Knuth remembers including it in an earlier volume of TAOCP, and cites Gardner’s contention that when interpreted properly the digits of pi convey the entire history of the human race. “In a way, you might say that the main purpose of my life, then, is to interpret the digits of pi correctly,” Knuth tells his audience. “What would be more important to accomplish in a lifetime?”

But the video’s description slyly suggests that instead, “This lecture will examine many interpretations of those digits, both proper and improper.”

Before long Knuth is sharing a mnemonic device for remembering the first digits of pi. You can obtain each of its first digits — 3.14159265358979 — by counting the number of letters in each word of the phrase:

“How I need a drink — alcoholic, of course — after the heavy lectures involving quantum mechanics.”

Next, he displays a book he calls “one of the great achievements of Oulipian literature” — a form of literature in which the writers follow severe (and sometimes mathematical) constraints. Its title?

Not A Wake: A Dream Embodying (pi)’s Digits Fully For 10000 Decimals

 Not a Wake book cover by Michael Keith (via Amazon)

The number of letters in each word from that title again correspond exactly to those first sequential digits of pi, and Knuth joyously reads from the book’s back cover. “It’s a play, a story, fantasies in modern verse and other writings, following without exception of the textbook math motifs…” That sentence, too, uses words where every word-length again matches to its corresponding digit in pi. “In the book,” Knuth adds, “he does it for 10,000 digits.” Then he’s reading from the book’s first poetic page…

“Now I fall, a tired suburbian in a liquid under the trees
Drifting alongside forests simmering red in the twilight over Europe…”

hands of Donald Knuth - screenshot from 2019 Christmas lecture (and Not a Wake book).

The digit 0 is represented with 10-letter words, and 11 can be represented with 11-letter words. “This is the language he calls Pi-lish,” Knuth says to a laugh. And what about the famous sequence in pi which has six 9’s in a row? The poet had written:

Blameless, bloodless, guiltless, ceaseless, limitless, boundless.”

Knuth’s audience applauds, as he continues flipping enthusiastically through the book. There’s essays, short poems, epigrams, even a movie screenplay — complete with dialogue — for a science fiction epic titled Zompyr Chronicle. And each and every word has exactly the number of letters as its corresponding digit of pi.

“The real tour-de-force, however, is a crossword puzzle…”

Wait, what? Yes, while still rigidly adhering to the word lengths specified by each digit of pi, a page in that book had suddenly offered the clues for a crossword puzzle — followed by a page with the actual grid where the answers could be entered. Its titled hinted that the answer words included book titles with the first letters of their words transposed — and sure enough, there’s both clues and answers for the Walt Whitman classic “Greaves of Lass” and that groundbreaking James Joyce novel, “Winnegan’s Fake.”

And towards the back of the book, there’s even a perfect Shakespearean sonnet…

Then Knuth reveals that there’s an especially tricky reference for pi in the index of his own book, The Art of Computer Programming, Volume 4A, “and then you have to figure out what on page 382 looks like pi.” The answer?

+00++-+++-000-

It’s pi in “maybe the most wonderful number system of all” — the balanced ternary number system, which uses the symbols 0,+ and – to represent digits in a base 3 system.

Puzzling with Pi

Eventually, Knuth turns to the pre-publication galleys for the newly published volume 4, fascicle 5, saying if you turn to any random page you’ll probably find a puzzle, “because it turns out that the kind of algorithms I’m describing here are best illustrated by their connection with puzzles.” And the emphasis in the book is not on how to solve the puzzles, “but how to create the puzzles.” Just as an example, he casually shows the audience a Sudoku puzzle he created where the already-filled-in numbers in the puzzle are 3, 1, 4, 1, 5, 9…

“I was able to get the first 32 digits of pi in there.”

hands of Donald Knuth - screenshot from 2019 Christmas lecture (pi hidden in Sudoku puzzle).

Could you do a Sudoku puzzle with more than 32 digits of pi? No — for the simple reason that the 33rd digit of pi is a zero, the one-digit that’s never used in Sudoku puzzles.

But next, he’s showing the cover of a book titled Exotische Sudoku — which not only used the digits of pi in a Sudoku puzzle, but even arranged them all in a circle. It’s an entire book full of Sudoku puzzles using only the digits of pi as the filled-in clues, while even observing an additional constraint — that the two diagonal lines of nine squares in the solution must also each contain each digit exactly once.

Exotische Sudoku book cover - from bol dot com

Knuth also shows examples of two puzzles that incorporate chess pieces. In “Knight Sudoko” the solution has every row, column, and box containing exactly three knights. The clues will show only some of the knights, along with a number revealing how many other knights they’ll ultimately be able to attack — and of course, Knuth constructed a puzzle in which those numbers are 3, 1, 4, 1, 5…

And then there’s a similar puzzle using bishops — and of course, the exact same pi-derived digits.

Then he’s off to KenKen puzzles, where the numbers in each set of adjoined squares will combine to give its specified solution (using the specified mathematical operator) — and In Knuth’s version, the clue numbers are 3, 14, 15, 9, 2, and 6… There’s a Kakuro puzzle — a kind of crossword puzzle with numbers — where Knuth challenged his readers to design one where the answers will be 31, 41, 59, 26, 53, 58, 97. There’s even a Hidato puzzle — where consecutive numbers are to be placed on a grid, but only on squares that are adjacent (either horizontally, vertically, or diagonally). Knuth challenged his readers to create just such a puzzle using only the digits of pi…

It’s a remarkable way to demonstrate that algorithms really will work on any set of digits — even 3.141592. But for his grand finale, Knuth revealed what may be the most remarkable puzzle of all — a slitherlink puzzle, a kind of puzzle which challenges its intrepid solvers to draw one contiguous line connecting dots in a grid, while only touching the number of sides on a “square” of dots specified by that square’s number. Knuth’s book had asked readers what surprise is concealed in one particular slitherlink puzzle’s solution?

And when Knuth revealed the puzzle’s jaw-dropping solution, he drew a long round of applause.

hands of Donald Knuth - screenshot from 2019 Christmas lecture (slitherlink puzzle solution is pi).

“Thanks a lot,” he told the audience triumphantly.

“And Merry Christmas.”

A newsletter digest of the week’s most important stories & analyses.