Softpanorama

Home Switchboard Unix Administration Red Hat TCP/IP Networks Neoliberalism Toxic Managers
May the source be with you, but remember the KISS principle ;-)
Bigger doesn't imply better. Bigger often is a sign of obesity, of lost control, of overcomplexity, of cancerous cells

Nikolai Bezroukov. Portraits of Open Source Pioneers

For readers with high sensitivity to grammar errors access to this page is not recommended :-)


Prev Up Contents Next

knuth.gifChapter 1: Donald Knuth: Leonard Euler of Computer Science

version 0.80


"Computer programming is an art form,
like the creation of poetry or music"

Donald E. Knuth[1974]

Contents

Let me make it clear from the very beginning: I really admire this man. Donald E. Knuth is not only Professor Emeritus of The Art of Computer Programming at Stanford University, the author of the multi-volume work-in-progress The Art of Computer Programming, five volumes of Computers & Typesetting, a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and the National Academy of Engineering and so on and so forth. Unlike many other bearers of a similar number of prestigious titles and published books, he is a unique lonely star among computer science researchers. I would say he is man of a stature similar to the stature of Leonard Euler in mathematics. Such men are not born every century...

Despite opinion of some overzealous (or in a permanent state of religious stupor) free/open software evangelists, free software existed long before Gnu project and the volume of it far exceeded the GNU project. Moreover the current free/open software is largely based on what has come before it. Professor Donald Knuth is one of the largest contributors to this pool of knowledge. Moreover, free and open programs are only as good as algorithms they are using. And dismissing his contributions to free software movement as irrelevant like "professional software freedom fighter" Richard Stallman once did (see Slashdot/2nd Annual Free Software Foundation Awards ) was at least disrespectful (even if we forget the fact that TeX is one of the most important free software programs ever written). 

It's amazing that despite the information explosion in computer science Professor Knuth is still trying to finish his monumental The Art of Computer Programming (TAoCP), a one-author written encyclopedia of algorithms and computer science. That really makes him  "The Last of the Mohicans" -- the last Renaissance man in computer science. He one of few who has managed to make contributions to a very diverse spectrum of  computer science topics. Among them:

Still no other book in computer science can be compared with his encyclopedic The Art of Computer Programming (TAoCP). It is one of the few books which remain relevant 30 years after the initial publication. I am convinced that every person who suspects that he/she has a programming abilities (and BTW an early interest/start is a good indication of abilities in any field, including programming) should buy or borrow the first volume of TAoCP and try to solve exercises after each chapter. The ability to solve difficult exercises from the first volume is a sure sign of people with substantial talent and can be a good self-test. It can help to decide whether it makes sense to dedicate yourself to career in computer science or not. Of course, computer science changed a lot since 1960th when TAOC was published; stagnation of CS departments is a fact that cannot be hidden. But despite that there are still a few areas in it where creativity matters and where talented people can make a significant contribution. As a side note, it is clear that becoming a quant in company like Goldman Sachs is not such a bright future as many assume.  Modern financial system in parasitic in a sense that it imposes huge cost on the society; one part of that cost is that large pool of top talent in the western world gravitates to financial firms. At the level of the society and aggregate economy, this is a waste  of resources: their activity adds little or no economic value.

Science including computer science is another story. It does has value to the society at large and Donald Knuth life is a good example what a single talented individual can accomplish besides buying a yacht with his name on it and a half-dozen of villas in different parts of the globe.


Introduction

Richard M. Stallman, Linus Torvalds, and Donald E. Knuth
engage in a discussion on whose impact
on the computerized world was the greatest.
Stallman: "God told me I have programmed
 the best editor in the world!"
Torvalds: "Well, God told *me* that I have programmed
 the best operating system in the world!"
Knuth: "Wait, wait - I never said that."

From rec.humor.funny.
submitted by ermel@gmx.de (Erik Meltzer)

While the  joke above is somewhat silly, it has a grain of truth in it: even among numerous computer pioneers in Stanford, Donald Knuth is a legendary figure. The figure with its own set of urban legends. For example, the old  anecdote from Alan Kay, one of the principal designers of the Smalltalk language, illustrates the point:

When I was at Stanford with the AI project [in the late 1960s] one of the things we used to do every Thanksgiving is have a computer programming contest with people on research projects in the Bay area. The prize I think was a turkey.

[John] McCarthy used to make up the problems. The one year that Knuth entered this, he won both the fastest time getting the program running and he also won the fastest execution of the algorithm. He did it on the worst system with remote batch called the Wilbur system. And he basically beat the shit out of everyone.

And they asked him, "How could you possibly do this?" And he answered,

 "When I learned to program, you were lucky if you got five minutes with the machine a day. If you wanted to get the program going, it just had to be written right. So people just learned to program like it was carving stone. You sort of have to sidle up to it. That's how I learned to program."

In his 2008 interview to InformIT  Donald Knuth recollected events in the following way:

Andrew: A story states that you once entered a programming contest at Stanford (I believe) and you submitted the winning entry, which worked correctly after a single compilation. Is this story true? In that vein, today’s developers frequently build programs writing small code increments followed by immediate compilation and the creation and running of unit tests. What are your thoughts on this approach to software development?

Donald: The story you heard is typical of legends that are based on only a small kernel of truth. Here’s what actually happened: John McCarthy decided in 1971 to have a Memorial Day Programming Race. All of the contestants except me worked at his AI Lab up in the hills above Stanford, using the WAITS time-sharing system; I was down on the main campus, where the only computer available to me was a mainframe for which I had to punch cards and submit them for processing in batch mode. I used Wirth’s ALGOL W system (the predecessor of Pascal). My program didn’t work the first time, but fortunately I could use Ed Satterthwaite’s excellent offline debugging system for ALGOL W, so I needed only two runs. Meanwhile, the folks using WAITS couldn’t get enough machine cycles because their machine was so overloaded. (I think that the second-place finisher, using that "modern" approach, came in about an hour after I had submitted the winning entry with old-fangled methods.) It wasn’t a fair contest.

As to your real question, the idea of immediate compilation and "unit tests" appeals to me only rarely, when I’m feeling my way in a totally unknown environment and need feedback about what works and what doesn’t. Otherwise, lots of time is wasted on activities that I simply never need to perform or even think about. Nothing needs to be "mocked up."

Donald Knuth probably received more prestigious computer science related awards then any other professor of computer sciences ;-), including the 1974 Turing Award, and the 1979 National Medal of Technology.

He holds honorary doctorates from more than 15 universities worldwide including prestigious Russian St. Petersburg University, the university were giants of mathematics hold the professorship including  Leonard Euler, the most prolific mathematician of the 18th century and maybe even of all time (he succeeded  Nicolaus Bernoulli as Professor of Mathematics of St. Petersburg University in 1733)

Around this time Johann Bernoulli's two sons, Daniel and Nicolaus, were working at the Imperial Russian Academy of Sciences in Saint Petersburg. On 31 July 1726, Nicolaus died of appendicitis after spending less than a year in Russia,[12][13] and when Daniel assumed his brother's position in the mathematics/physics division, he recommended that the post in physiology that he had vacated be filled by his friend Euler. In November 1726 Euler eagerly accepted the offer, but delayed making the trip to Saint Petersburg while he unsuccessfully applied for a physics professorship at the University of Basel.[14]

Euler was phenomenal and after he became blind in 1775 he still managed to produce, on average, one mathematical paper every week. He spend in St Petersburg University his most productive years  until died in St. Petersburg at 1783 at the age of 76.

That's probably an example for Knuth to strive for, as Leonard Euler published 866 books and articles that represented about one third of the entire body of research on mathematics, theoretical physics, and engineering mechanics published between 1726 and 1800. Among other things he modernized mathematical notation including the introduction of now standard symbols  \pi  and e. An interesting, but little known fact is that in 1962 Knuth obtained 1,271 digits of Euler's constant, using the Euler-Maclaurin summation.

Actually the analogy between Donald Knuth and Leonard Euler is deeper than Lutheran religion, tremendous productivity and groundbreaking contributions. Both has interest in things quite remote from the their main field: Leonard Euler was interested in cartography (historians believe that this contributed to his early blindness) and spent a lot of time and effort on non-mathematical studies; Donald Knuth also spend huge amount of time and effort outside his major field while he developed the TeX and Metafont (written in WEB for Pascal) -- the major open source typesetting system that become a standard de-facto in mathematics and computer science. He also published 3:16 Bible Texts Illuminated.

Like Euler believed in the esthetic value of mathematic theories, Knuth believes that preparing programs for a computer can be an aesthetic experience, much like composing poetry or music. As for music he probably knows what he is talking about: he plays a custom-made pipe-organ (this sixteen-rank organ was designed and built for his home by Abbott and Sieker of Los Angeles, California, as their ``Opus 67.'' It has 812 pipes, separated into three divisions).

A the same time Knuth is a tragic figure.  He tried to write a monograph on topic that is far beyond comprehension of a single man. Ground in computer scoences shifted several time after he wrote the first three volume. And it is unsuprizing that he lost traction and  shifted more to combinatorics., which is more stable field.

And while the first three volumes were produced relatively quickly (1963-1968), the forth volume (still unfinished) took all his time from 1968 till 2018. That's a Guiness record for whiting the next  volume. Alexandr Dumas has  a novel  Twenty Years After. Here we have the forth volume which is 50 years after ;-).

Now it is clear that Knuth will never be able to complete this monograph -- the technology developed too quickly and the field became too diverse. In January 10, 2019 he reached the age of 81. At this age it is difficult to work in the field of mathematics and system programming. This inability to finish the work he devoted a large part of his life is definitely a tragedy. The key problem here is that now it is simply impossible to cover the whole area of ​​system programming and related algorithms for one person. But the first three volumes played tremendous positive role for sure.

Also he was distracted for several years to create TeX. He probably needed to create a non-profit and complete this work by attracting the best minds from the outside. But he is by nature a loner, as many great scientists are, and preferred to work this way.

His other mistake is due to the fact that MIX - his emulator was too far from the IBM S/360, which became the standard de-facto in mid-60th. He then realized that this was a blunder and replaced MIX with more modem emulator MIXX, but it was "too little, too late" and it took time and effort as modern CPU architecture became very complex indeed. Also Knuth being Knuth tried to create "ideal" instruction set and that required several revisions (mostly additions of instructions). So the first three volumes and fragments of the fourth is all that we have now and probably forever.

Not all volumes fared equally well with time. The third volume suffered most IMHO and as of 2019 is partially obsolete. Also it was written by him in some haste and some parts of it are are far from clearly written ( it was based on earlier lectures of Floyd, so it was oriented of single CPU computers only. Now when multiprocessor machines, huge amount of RAM and SSD hard drives are the norm, the situation is very different  from late 60th. It requires different sorting algorithms (the importance of mergesort increased, importance of quicksort decreased).

While writing volume 3 he also got too carried away with sorting random numbers and establishing upper bound and average run time. The real data is almost never random and typically contain sorted fragments (often in inverse order). He also never researched perforce of very large data sets as memory at the time of the writing th book was really minuscule, less then a modern cell phone. Some algorithms, like quicksort,  self-poison  themselves on large data sets, regularly creating "worst case" subsequences (this effect is clearly visible, if you try to sort, say, the last 30 years of S&P500 data using quicksort.) In general, it is far to say,  that Knuth overestimated the practical value quicksort and thus pushed the discipline in the wrong direction.

The other  problem with Knuth is that he missed the rise of Unix and for some time was pretty foreign to Unix philosophy. although later he used Linux laptop for his  research. 

Prev Up Contents Next


Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D


Copyright © 1996-2018 by Dr. Nikolai Bezroukov. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) in the author free time and without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.

This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to make a contribution, supporting development of this site and speed up access. In case softpanorama.org is down you can use the at softpanorama.info

Disclaimer:

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.

The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 16, 2019