Donald Knuth on work habits, problem solving, and happiness (2020) | Hacker News Reader

Donald Knuth on work habits, problem solving, and happiness (2020)

shuvomoy.github.io

634 pointsThursday24161 comments

> My mother is amazing to watch because she doesn't do anything efficiently, really: She puts about three times as much energy as necessary into everything she does. But she never spends any time wondering what to do next or how to optimize anything; she just keeps working. Her strategy, slightly simplified, is, "See something that needs to be done and do it." All day long. And at the end of the day, she's accomplished a huge amount.

This strategy is remarkably powerful and I've used it to great effect in my career. Committing yourself to pushing forward every single day, even if just a little bit, and always just peeling off one single thing you can do next (even if it's tiny yet takes you all day) has a dizzying compounding effect.

This is effective because analysis paralysis is mentally draining.

We tend to think/optimize in terms of time. But I've found it helpful to optimize for mental energy, which is often the limiting factor.

This carries over to social anxiety as well -- you tend to overthink what people think and such -- the more you do things the better you naturally get from experience as well.

If you're doing, do you have time to overthink?

> We tend to think/optimize in terms of time. But I've found it helpful to optimize for mental energy, which is often the limiting factor.

I love this. Very succinct and insightful.

https://news.ycombinator.com/item?id=31500342

Wonderful, thank you.

That article is from On Managing Yourself (2 vols) which is part of the HBR 10 Must Reads series. You will also find On Managing People (2 vols) and On Communication (2 vols) from the same series pretty useful.

https://hbr.org/2007/10/manage-your-energy-not-your-time

My mom is exactly the same and I really admire her for it.

Until eventually someone invariable has to clean up your mess due to awful choices.

But why should you care?

You've moved on with your trail of collateral damage by then, reaped the benefits and the fixer will subconsciously take the blame for any problems from outside observers.

A.k.a. "Move fast and break things".

Don’t know why you’re being downvoted, but this agency effect is real. The implicit assumption that rarely works out behind this “git ‘er done” is the “small” tasks picked up have already been organized into such tasks from a decomposition of the complex problem the tasks are part of.

This is why for example, I see fancy CICD pipelines covering for static component dependencies locked into a hard coded version of components. Completely breaking a core value proposition of the pipeline, but someone got the story points and moved on. It turns out that small task of putting the project into the pipeline should have been decomposed further. Oops.

This philosophy is a power tool and like any such tool, you take care in where you point it, and it will serve you well. Point it in the wrong direction however, and it will also happily blindly eviscerate you with no malice.

or as we say at my job "JFDI". Just Do It. Stop Faffing. Just Do It. Ok. It's done. Now we can move on.

Step 1. Create a TODO list Step 2. Do the TODO list.

... there is no Step 3

Step 3: Update the TODO list

Step 4: Go to Step 2.

+1 for getting GOTO in there.

"Long-term consistency trumps short term intensity" - Bruce Lee https://www.dannyok.com/blog/2015/9/26/long-term-consistency...

Unless we are talking about High-intensity interval training.

I know you’re being facetious, but actually any form of exercise is a great example of Bruce Lee being correct!

This only works for simple tasks (can be brute forced), and ones you've done before (you know steps that lead to goal), and those with greedy strategies (heuristics).

Every long journey begins with a small step. You won't do the journey unless you are willing to do that small step. And the next.

This is exactly how I approached Leetcode. TBH the grind has had satisfactory effects even though the immediate practical impact is just for interviewing. I don’t use it as a tool for interviewing, just as a tool of list of things to get done. I should just pour more energy into it and do it every day.

I also am stealing this principle ‘My scheduling principle is to do the thing I hate most on my to-do list’

As someone with rural/countryside roots, I recall similar advice on physical labor: it is best to work at a steady, consistent pace all day long without getting sweaty or breathless. You'll avoid (or postpone) dehydration, remain more alert and calm, and thus it is much easier to switch tasks immediately.

As a tree planter of several seasons, I've realized that this advice works remarkably well. Pushing yourself, sweating, drinking stimulating beverages instead of plain water etc seems to give you an edge while planting, but it's kind of deceptive in the long run IMO. Steady, moderately paced, but consistent, non-stop work is more effective in the grand total.

Then again, all this might come down to whether one is a "long distance runner" or a "sprinter" by personality and bodily characteristics. I guess I'm somewhere in between, but, approaching 40, these "100 meters in 9.2 seconds" daily life dashes are somehow starting to lose their appeal. Howdy, middle age!

This resonates with me, but sadly not with modern culture that is so hell-bent on both optimization and PUSH PUSH PUSH! all the time. It's ridiculous.

This approach is actually best for learning/studying anything Eg. Martial Arts, Mathematics etc. Regular, Mindful and Consistent practice without over-straining is the key. Intensity should pick up only for key events likes Exams, Tournaments etc. and maintained only for a short duration followed by relaxation.

"Do the Next Right Thing" is what I try to do.

> Recently, I came across a few old and new interviews of Donald Knuth

I have developed the conclusion that reading digestive summary from original source materials is ultimately ineffective for me at this stage of the life.

Unfortunately, the author did not provide links to these interviews.

For anyone who is writing a summary from other source material, please do provide references. That's one of the things I learned churning out low quality academic papers in PhD study.

probably the Lex Fridman podcast interviews:

https://www.youtube.com/watch?v=2BdBfsXbST8 https://www.youtube.com/watch?v=EE1R8FYUJm0

the second one is definitely where the last paragraph in the article is from. Weird that the interview is dated 2021-09-09 and the post is 2020-04-30?

He also did an interview for the Web of Stories project which is available on YouTube and has his thoughts on his life and various other curious topics.

https://www.youtube.com/playlist?list=PLVV0r6CmEsFzeNLngr1Jq...

Wow, Lex has gotten some of the greats on his podcast. I should probably give it a go. The few episodes I've seen were more shallow than I was looking for as an engineer, but I assumed that was because he's helping bring these interviews and ideas to a wider audience.

if you're looking for more technical ones the two interviews he did with Crhis Lattner on compilers are great. Francois Chollet and Schmidhuber and other ML related interviews were good also.

But he does seem to be doing less and less of the scientific interviews which is a little bit of a shame given the unique access he seems to have.

Lex and Joscha Bach episodes were fascinating to me as well.

They sometimes go deep, but that is more at the discretion of the interviewee than Lex. Lex is usually asking questions about topics he has only tangencial knowledge in but is the expertise of the interviewee.

The Chris Lattner episodes are great, and James Gosling had some fun stories in there, and Kernighan had a good interview as well.

And he always asks them the question "What is life?"

Donald Knuth interviews are so interesting, but would like to particularly highlight this little piece of advice, out of this great playlist:

"Donald Knuth - My advice to young people": https://youtu.be/75Ju0eM5T2c

Complete Playlist - "Donald Knuth (Computer scientist)" [97 videos]:

https://www.youtube.com/playlist?list=PLVV0r6CmEsFzeNLngr1Jq...

Also the "Oral History of Donald Knuth" from the Computer History Museum is great.

"Oral History of Donald Knuth Part 1": https://youtu.be/Wp7GAKLSGnI

"Oral History of Donald Knuth Part 2": https://www.youtube.com/watch?v=gqPPll3uDa0

Plus..

"Donald Knuth Interview 2006": https://github.com/kragen/knuth-interview-2006

"An Interview with Donald Knuth": https://www.ntg.nl/maps/16/14.pdf

"Interview with Donald Knuth": https://www.informit.com/articles/article.aspx?p=1193856

This somewhat "colourful" page also tracks a few: http://www.softpanorama.org/People/Knuth/donald_knuth_interv...

PS: The story that he told Steve Jobs he was "Full of shit" is not true.

"Donald Knuth never told Steve Jobs that he was full of shit"

https://news.ycombinator.com/item?id=2634635

There's one interview where he talks about a special sofa that he uses to read (and write, I believe), but I haven't been able to find it with all my Google-fu.

Well he says he has his special black chair...

"Donald Knuth: Writing Process": https://youtu.be/vG0D-kKTF1g

Ironically, a significant portion of Knuth's lifetime work consists of digested summaries of original source materials.

Do you have quick summary of Knuth stating this? Just want to know, curious.

He has indeed said that, I can confirm that much. It should be easy to find in one in the interviews.

Yes it should be easy to find in 50+ hours of video content.

In addition to the other post in this thread mention that it's time consuming to go through the list.

Fundamentally, that work can be saved by the original author spend negligible amount of energy to provide the reference.

When I see people hiding information, or forgot to provide links, I am thinking a bit of human intellectual energy is wasted for no good reason...

He doesn’t have to state this. Look at his work.

The complaint is not the summarization, it is the lack of citation. I see no irony in this light.

I wasn't referring to the complaint, it was a reference to the output of Knuth not being particularly accessible if you don't like reading digested summaries, because a big part of what he set out to do is to summarize academic research across a wide range of topics.

I guess it's like rain on your weeding day.

One of the quotes seems to mention to that, where he says he digests a lot of papers to add a small part to TAoCP, since his aim is to write books that cover a the breadth of computer science (which necessarily cannot be as deep as these papers go).

(In his digestive summaries, Knuth does provide citations, to be clear)

I guess I don't understand why someone would make the contrary assumption about famous academic work.

For sure, also I don’t assume people know much about Knuth or expectations for academic work.

His citation lists at the back of each book are immense.

Synthesizing or summarizing? There is a difference.

> ...it turns up in Philippians 3:16, where the writer says that:

> "You don't race to get to the goal; the process of racing itself, of keeping the pace, is the real goal. When I go on vacation, I like to enjoy the drive."

> In Christian churches I am least impressed by a sermon that talks about how marvelous heaven is going to be at the end. To me that's not the message of Christianity. The message is about how to live now, not that we should live in some particular way because there's going to be pie in the sky some day. The end means almost nothing to me. I am glad it's there, but I don't see it as much of a motivating force, if any. I mean, it's the journey that's important.

---

This is Philippians 3:16: "Only let us live up to what we have already attained."

It's hard for me to connect that to the paraphrase given above. Furthermore, the previous few verses (12-14) of that same chapter seem to be more goal-oriented, than process-oriented:

"Not that I have already obtained all this, or have already arrived at my goal, but I press on to take hold of that for which Christ Jesus took hold of me. Brothers and sisters, I do not consider myself yet to have taken hold of it. But one thing I do: Forgetting what is behind and straining toward what is ahead, I press on toward the goal to win the prize for which God has called me heavenward in Christ Jesus."

Also see 1 Corinthians 15:19:

"If only for this life we have hope in Christ, we are of all people most to be pitied."

So, Knuth wrote this rather unusual book called "3:16" in which he took every chapter-3-verse-16 in the Bible (where chapter 3 is too short for that, he continued past the end into chapter 4 in the obvious way), thought about it a lot and wrote down his thoughts, and also commissioned eminent calligraphers to render his translations of all those verses.

(He was inspired, if that's the right idea, by the notion of stratified sampling in statistics. He called this application of it "The Way of the Cross-section".)

Here are a few extracts from what Knuth says about Philippians 3:16 in that book, which may help explain.

"English translations of verse 16 tend to be quite different from each other, because Paul's original Greek words are difficult to render in our language. A literal translation goes something like this: 'Hey, to what we've reached, by this to march!'"

(Presumably the "live up to" in the translation you quote is the "by this to march" in his literal translation. So part of what's going on is that Knuth thinks, while the translators you're quoting don't, that the notion of progress in the Greek metaphor there is essential to what he's saying.)

"Putting all these words together, we can see what verse 16 means: 'Let's keep progressing from the point we've reached.'"

(Making it more explicit. I have to say that the foregoing paragraphs in Knuth's thoughts on this verse don't particularly explain why he thinks it means that rather than, say, "stay on the same road" or "continue marching in the same pattern" or something of the kind, which seems to be the sort of idea most English versions embrace.)

"Paul's main point [sc. in this verse and the chapter as a whole] is that the Christian life is a process of continual striving for greater faith, for greater knowledge of God."

(This seems pretty fair to me. Yes, what comes before verse 16 talks about a goal, but it also emphasizes that it's a goal not yet reached, still the object of constant straining.)

It still seems hard to reconcile what the rest of Philippians 3 actually says with Knuth's "you don't race to get to the goal". (For the avoidance of doubt, in "3:16" he says in so many words "he [sc. Paul] continues to run toward the goal", so it's not like he's missed the aiming-for-the-goal idea here.) Here's my best guess at what he's thinking: Paul doesn't reckon he's reached the goal; he clearly doesn't think anyone else has reached it; indeed, it seems pretty clear that he doesn't expect anyone to reach it before their death. So (I conjecture Knuth thinks) what's the point of all that striving and straining? It can't really be that we need to strive and strain in order to be saved -- Paul seems pretty opposed to that sort of idea, elsewhere. So the real point of the striving and straining must be the effect it has on our lives here on earth.

That's my best guess at Knuth's thinking, anyway. He doesn't make it explicit, at all. Another possibility, of course, is that when he said what the OP here quotes him as saying he was only sketchily remembering what Philippians 3:16 says and attributed to it something related to, but incompatible with, what it actually says, and that if you pointed him at the actual text of the chapter and his own analysis of it in 3:16 he'd say something like "oops, yes, I shouldn't have said it said that".

(Disclaimer: I am not myself a Christian, though I was one for many years; you may or may not wish to discount accordingly anything I say about theology or exegesis. Also: my main reason for writing this comment is that I suspect that any HN readers interested in Knuth's thinking about this kind of thing would enjoy "3:16".)

It's getting off topic, but I love how we interpret Knuth's works like those of Rashi[1] interpreting the Talmud:

His commentary on Tanakh—especially on the Chumash ("Five Books of Moses")—serves as the basis for more than 300 "supercommentaries" which analyze Rashi's choice of language and citations, penned by some of the greatest names in rabbinic literature.

[1] https://en.wikipedia.org/wiki/Rashi

Yeah, I did feel a little weird writing commentaries on Knuth's writing just like he was writing commentaries on Paul's. Fortunately no one thinks I am obliged to regard Knuth as perfectly free from error.

(Speaking of not being perfectly free from error, in my earlier comment I wrote "if that's the right idea" but of course I meant "if that's the right word", but I didn't notice until after it was too late to edit.)

> It can't really be that we need to strive and strain in order to be saved -- Paul seems pretty opposed to that sort of idea, elsewhere. So the real point of the striving and straining must be the effect it has on our lives here on earth.

This interpretation appeals to me.

> One day, when I realized how hard it was to find any reason for my current unhappiness, I thought, "Wait a minute. I bet this unhappiness is really something chemical, not actually caused by circumstances.*" I began to speculate that my body was programmed to be unhappy a certain percentage of the time, and that hormones or something were the real reason behind moments of mild depression."

This is exactly what happens to me with my dysthymia. The intensely heavy body feeling (medical term: "psychomotor retardation") and low energy aren't really problems in themselves, it's when I "buy into them" that it really goes downhill. The problem is that it does kinda suck and makes it hard to concentrate and do things.

Unfortunately my mood has been generally very low since about age 9 to 11 unfortunately, and I'm 27 now. I don't see much value in life or in others or relationships (even though I am married!). So that combined with the physical symptoms makes it a difficult and slow life.

How did you value another enough to enter into marriage with them? What was that decision like?

It just seemed like the obvious thing to do. We are more like very stable roommates that hug, rather than lovers.

That’s a poetic description of what sounds like a wonderful relationship. Hats off to you!

(Disclaimer: Please take what I saw with a grain of salt - I'm just a stranger on the internet, not a doctor. No disrespect intended to you or anyone.)

Have you checked if you might have other possible conditions? I too "thought" I was mildly depressed for several years (I'm in my early 20s now). Turned out to be (undiagnosed) ADHD that held me back from working "properly" (due to procrastination/planning issues) while making me ambitious, hence making me sad/disappointed/frustrated. (I hope to get a formal dx soon, apparently medication can help a very decent bit)

There is a lot of overlap between the two, but I have more depression symptoms than ADHD ones. The latter doesn’t seem likely to me nor who diagnosed me

If it doesn't seem likely to you that's likely fine. I forgot to mention, in my case I was diagnosed as depressed by the psychiatrist (wrongly ofc).

The biggest tell for me is the psychomotor retardation: general slowness of movement and extreme heaviness feeling

His "0.8 is enough" idea is close to an observation I made a few years ago, that the Dunning-Kreuger effect seems to reflect an ideal breakpoint for social stratification.

People low on the curve drift towards evaluating themselves at ~0.75 (round to Knuth's 0.8), and those above that marker drift towards it as well.

So when we are actually around the 80th percentile of anything, we're in the sweet spot everyone else's self-image trends towards.

It makes sense too - we're very social beings, and being an outlier is inherently isolating.

To Knuth's example - if he were 100% happy all the time, that could actually cause more social integration issues than being mostly happy (80%). For example, "Congrats on the funeral, it looks awesome!"

Typically, good enough is perfect.

I still read TAOCP, particularly vol 4, for fun from time to time, but I have to admit that the days are long gone when an ordinary engineer needs to study algorithms in depth. The vast number of libraries and services are good enough that most people just need to know a few terms to function adequately for their jobs. I guess it's a good thing as it shows how robust the software abstractions are, in contrast to mathematics. It's just that I feel quite nostalgic about the countless days I spent understanding, proving, and implementing fundamental algorithms and data structures.

There will always be a "higher" type of engineers who want to read TAOCP and similar.

My issue with the books is that they're actually quite long winded even by what you'd expect from the tone.

There's some really cool stuff in them, obviously, but I think they're objectively not very good textbooks for any purpose.

Then again I'm coming from a background of physics rather than mathematics so I'm not set out for a real battle of wits when it comes to constructing proofs.

I think they are excellent textbooks if your goal is to learn all about algorithms. And by this I mean he takes these great tangents into slightly different derivations that lead to wildly different complexities. Or why somethings are actually ambiguous or some interesting special case.

And maybe even more importantly, a great collection of problems to work through. I think it is actually an underappreciated text nowadays.

My gripe is that there is an order through them that is an excellent textbook, but the lexical order through the book is usually very long winded and meanders immensely.

Meandering through topics is good, but he meanders through style as well: sometimes he was in a mathematical mood, sometimes he was feeling more practical. I think it's better to intuit first then formalize, Knuth likes to do these in groups of pairs rather than a pair of groups.

Knuth is not the worst at this, but the lost potential is the greatest in his writing.

Related to your higher type of engineer: http://employees.oneonta.edu/blechmjb/JBpages/m360/Professio...

It’s a good short story if you’ve got 20min.

Excellent suggestion. I enjoyed it. Just one question. How the hell does anyone read all that in 20 minutes?

Maybe 40min? It's been a long time since I've read it.

TAOCP is meant to be a textbook, a reference, and a historical account of algorithm development. I find it most rewarding to pick the most interesting part to me at the moment to read. I also ignore the MMIX code (even though I did work through the MMIXware book) and focus on first intuition, then code, and then the math that teaches me new ideas or new methods.

I find the MMIX code less relevant to my line of work now as getting down to machine-level optimization requires a whole new different suite of tools. The ensuing optimizations on modern CPUs seem deviated from what the MMIX code can help.

Yeah, TAOCP's casual style puts me off too. Side by side with high watermarks in technical writing like The C Programming Language, Specifying Systems, or Loney's Elements of Coordinate Geometry its shortcomings are pretty obvious. But that's an opportunity for a clever editor to make an actual reference manual out of TAOCP sometime in the future.

Knuth's a good, engaging writer, but TAOCP's content and typography are definitely better thought out than the prose.

EDIT: Just remembered a BBC interview with a philosophy professor about Kant. Apparently Kant is criticized for being really verbose. The professor's retort was he sensed Kant had so much to say and so little time to say it that he didn't edit very carefully, giving it a similar kind of bloated, meandering quality. Even so, Kant is held up as one of the GOATs, because in the end it's the content that counts.

The most valuable part of TAOCP, for me, is its writing.

I've never read anything that is more precise or intuitive. TAOCP is also pleasant to read.

It's the book that I go back to once a while after being bothered by the sloppiness in the documents and papers and many other written materials consumed everyday. Reading it gives a sense of enlightenment that regardless of all those poor writing, there is hope to reach the clarity that I have the deepest desire for.

My only gripe with TAOCP is its usage of MMIX.

If I where to ask “So what should he have used instead?” it would quickly derail this thread. There would be no consensus. Knuth probably foresaw this exact problem and more.

Half of people would say Javascript and the other half Python. :)

Yes, I know those languages didn't exist at the time Knuth was forging his books.

Yeah, if you read the intro to Volume 1, he specifically calls this out as an issue. I personally think he's taking a subtle dig at Numerical Recipes here, which did take the "modern" language approach.

Yep, at least he could use an OOP language, and some niceties like builders, decorators, factories, 15 layers of abstraction and indirection so everybody knows it's pro grade stuff. :)

Listening to interviews and reading Donald Knuth has profound effect on my mental state. It's like diving into another dimension which have concerns that are orthogonal to my daily business. It's an immense pleasure for me to rediscover this mental state from time to time. And this is to me Donald Knuth greatest achievement: To let us look into his thinking process and putting words to guide us through it.

> the days are long gone when an ordinary engineer needs to study algorithms in depth

Except to pass the interview screens at high-profile tech companies?

Most leetcoders simply memorize one or two solutions instead of studying algorithms holistically. I suspect that many would spend time understanding that generating gray code can be mapped to mixed-radix number system (nor should us anyway, albeit it's really really cool). Leetcode does not require understanding of advanced data structures either. Instead, it's full of clever tricks and specific solutions with which entry-level ACM participants are well versed.

I think it's harder to memorize hundreds of solutions than it is to understand a few tens of algorithms and their use cases.

Like with math, it's easier to learn to solve problems than to learn by heart hundreds of potential problems the teacher might give you on an exam.

> I have to admit that the days are long gone when an ordinary engineer needs to study algorithms in depth

Even that I architect and write software for a living, I don't consider myself an engineer, but a computer scientist. I've studied Computer Science in University, not Engineering. I like to understand how things work, why they work, how would they work if anything would be changed. I like to try, discover and do new things, not new only for me, but things which weren't done previously. And that is impossible without a solid understanding of theoretical principles and continuous learning.

If I wouldn't be into computers, I could see myself as a mathematician, physicist, biologist, doctor, artist or architect but not as an engineer since I do like to go deeply to the root of knowledge, not just apply the said knowledge.

I see a great value in engineering mentality, but it's just not for me.

One of my favorite facts about Knuth is how rarely he checks email!

https://www.calnewport.com/blog/2008/07/17/bonus-post-how-th...

Fast responses to email was just cited as a key factor in founder success in Cowen's "Talent". He quoted Altman, who apparently ran some rudimentary data analysis based on his own emails while working at Y Combinator. Obviously Knuth is not successful as a founder.

I don't know, he was a co-founder of computer science.

> He quoted Altman, who apparently ran some rudimentary data analysis based on his own emails while working at Y Combinator.

... which would mean "Fast responses to email from YC Partners was just cited as a key factor in founder success" ...

yeah cuz tyler is the authority on this matter

My favorite Knuth fact is that he thinks P = NP. [1][2] That's a very contrarian view.

[1]: https://youtube.com/watch?v=XDTOs8MgQfg

[2]: https://www.informit.com/articles/article.aspx?p=2213858&WT....

That's interesting. But my favorite Knuth fact remains the fact that he published his first technical paper in Mad Magazine.[1]

[1]: https://news.ycombinator.com/item?id=20351772

he has "a wonderful secretary who looks at the incoming mail"

Every day I look at the things that I'm ready to do, and choose the one that I like the least, the one that's least fun — the task that I would most like to procrastinate from doing, but for which I have no good reason for procrastination.

I'm not sure I've seen this approach to combating procrastination before. I can see how it might work: once you've completed the thing you least wanted to do, you might feel relief that the distasteful task is done and you can then dive into other stuff without that nagging you in the back of your mind.

I think I will give this a try...

If it's your job to eat a frog, it's best to do it first thing in the morning. And If it's your job to eat two frogs, it's best to eat the biggest one first.

Mark Twain

Beat me to posting the same quote. I don't always manage to follow it, but it has helped me sometimes.

The key is asking "Is there a reasonable chance that this unpleasant task/expensive purchase/other potential PITA will go away if I put it on a list and continue to avoid it?" If the answer if yes, then procrastination can actually be a good thing. Kicking a can down the road can actually be a pretty good strategy.

Otherwise, you might as well bite the bullet, especially if there's some advantage in doing it sooner rather than later.

> "The best test of when I'm about ready to solve a problem is whether or not I can think about it sensibly while swimming"

My personal variant is "when I don't have problems to solve while I'm cycling it's time to look for a new job" :)

> they haven’t learned the fundamental ideas of algebra

I'd very much love to know exactly what Knuth considers the "fundamental ideas of algebra"!

Perhaps the eponymous fundamental theorem of algebra is a good place to start.

https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra

From the same page: "the Fundamental Theorem of Algebra is neither fundamental, nor a theorem of algebra"

For more on this theme, see: https://www.math.nyu.edu/faculty/edwardsd/carnegie.pdf

It sounds like he's just talking about using variables to solve equations. I think the point he's making in that section is just about learning a good process so you can solve harder and harder problems, e.g.

Problem 1: Two numbers add to 100, one is 20 larger.

Smart student: oh, I see, 60 and 40.

Dumb student Knuth: x + y = 100 and x = y + 20, solves to x=60, y=40.

Problem 2: Four numbers sum to 1024, one is half the sum of the other three less 17, one of the others...

Smart student: uh, I don't see the answer.

Dumb student Knuth: w + x + y + z = 1024, w = (x + y + z)/2 - 17, ... solved it.

x + y = 100

x - y = 20

2x + y - y = 120

2x = 120

x = 60

y = 100 - x

y = 40.

Algebra goes so much deeper than this. I had so much trouble with my compilers class because my professor expressed all the ideas and principles of compilation using algebra.

So I second OP's comment - I wish there were a course one could take on algebra itself - not merely numeric expressions with variables.

> I wish there were a course one could take on algebra itself

Depending a little on just what you mean, that's likely the upper-division undergraduate math department course called "Algebra" at most universities. Groups and rings and such.

> the upper-division undergraduate math department course called "Algebra"

And be careful what you wish for - the way eighth-grade algebra hurt your brain when you were 13 will be nothing compared to the way abstract algebra will hurt your brain when you're 20.

... in a good way.

I liked "high school" algebra okay, but group theory was fun, even if homework was sometimes spending hours and pages to wind up with a 10 line proof.

In my case abstract algebra was much easier to grasp than polynomials with no context.

I thought of that, but it sounded like it was just studying particular mathematical structures -- not learning "how to read arbitrary algebraic expressions".

Or perhaps algebraic expressions in different mathematical specialties are differentiated enough to make knowledge about how to read a given expression mostly non-transferable?

Ah, to my mind "algebra" is the structure. It sounds like you want a survey of mathematical notation?

> a survey of mathematical notation

YES!

I think in some part you had it right that it differs a bit by specialty, but I think the bigger part of it is that the syntax doesn't mean much without the concepts behind it. Notation is a way to compress concepts that are already understood in elaboration.

Being able to recognize notation without the conceptual underpinning might be useful in directing you towards what you need to learn for a particular task, but it's going to be difficult to learn without anything to hang it on. That said, maybe what you actually want is a math notation OCR that can direct you to documentation for possible interpretations.

What are the principles of compilation using algebra?

Yes of course it does and Knuth is well aware (as am I to a lesser extent), but I’m just saying I don’t think it’s relevant to the point he’s making here.

After reading the relevant article section, I'd guess he's talking about the idea that problems can be mapped onto mathematical structures, allowing use of pre-known rules within said structure, for transformation and identity and so on, such that the problem can then be solved. He's saying that for simple problems if you're clever you can intuit the solution without that mapping/manipulation/solve process, but as a result you can never see how to solve more complex problems. Implication being that if you had been slightly less smart, you'd end up understanding mathematical structure earlier in life, with associated benefits in terms of success in certain fields. Like: https://en.wikipedia.org/wiki/Abstract_algebra

> trying to work the concepts out in my own mind and to anticipate what the authors are going to say before turning each page. I usually fail to guess what the next page holds, but the fact that I've tried and failed makes me more ready to understand why the authors chose the paths that they did

TIL Donald Knuth operates a bit like GPT-3 but for research paper narrative.

I see it differently. It's not prediction based on anything statistical but based on one's understanding.

I've made it a habit to ask myself what I expect the output to be for any programming operation, and why. It forces me to gain clarity into my mental model of what's happening, and it immediately highlights deficiencies in my model when it's proven wrong.

I ask the same of others when I pair program with juniors or interviewees. I find super useful all around.

> not prediction based on anything statistical but based on one's understanding

It is still statistical. You still want to predict a distribution over expected next token.

However, the function needed to estimate the likely next tokens are not simple max over enumerated next tokens like in a language model. It's more like a transition model in reinforcement learning.

> It is still statistical. You still want to predict a distribution over expected next token.

The fact that a process can be described statistically does not make the process itself statistical.

With the current craze of neural networks people would like to think that anything that happens in the Universe is statistical. But it's really not.

Quantum mechanics is probablistic. But the probabilities are deterministic.

This guys name shows up on almost every important combinatorics result . amazing how much he has done

that's got to be a typo: he is a venerable wizard, but combinatorics is a field far more vast than algorithmic things, often dominated historically by Hungarians

> I try to do a good job at whatever I'm doing, because it's more fun to do a good job than not.

Yes it's "fun" and I'll add that it's a great primer for the more significant tasks.

> it's selfish to keep beautiful discoveries a secret.

I found a beautiful thing recently and planned to do a write-up on it eventually, but I know I might get distracted. So I'll share the beauty here since I don't want to be selfish!

In K means clustering you know you've stabilized if centers t = centers (t-1). Stabilization has occurred because no clusters were reassigned during the lloyd iteration. People already know this. In many implementations of k means clustering you'll find this check in the body of the loop as a special case which means the loop should end. You can't have this as the condition of the while loop because you don't yet have a centers t-1 on your first loop. Actually you can by supposing a hypothetical all nil cluster definition prior to initialization, but people don't tend to do that. That failure to do that is ugly in the same way that Linus refers to code which uses special casing as being ugly. It doesn't apply the same procedure to every iteration. They should do that and it would make the code more beautiful. However, that is not my discovery, but just a preference for beauty and consistency.

What I noticed is that the equality check is actually giving you a bitset that tells you whether any of the centers was changed. This is a more general idea than just telling you that you can stop because you are done. It is telling you /why/ you aren't done. It is also deeply informative about the problem you are solving in a way that helps the computation to be done more efficiently. I want to show it being deeply informative. So I'll touch on that briefly and then we can revisit the simplicity.

Clusters being reassigned tells you the general location that have the potential to need future reassignment. For example, in the range of 1 to a 1,000,000 on a 1d line if a cluster at 10 moves, but there is a cluster at 500, then you know you don't need to look at reassignment for any cluster above 500. I mean this in two sense. One is that nothing in clusters past the 500 can change. So you don't need to look at them. The other is that clusters past the 500 cluster can't even be nearer. So you don't have to find the pairwise distance to them. In the assignment stage of the lloyd iteration you don't even need to look at everything above 500. So you not only reduce the amount you need to look at in the N dataset items. You also reduce the number of k clusters centers you need to compare them to. In the 1 to 1,000,000 domain example for stuff below 500 that is probably going to be more than 99% of your data that you can skip and the vast majority of clusters that you don't even to need to check distance for.

Returning to the simplicity discussion it means you can write the loop without the special casing. Instead of a break when stabilization has occurred you have a selection criteria function which tells you the selection criteria for that step of the lloyd iteration. Obviously at the initialization stage we went from no definitions to k definitions. So the selection criteria function is well defined even for the very first iteration on an intuitive level.

Why do I find this beautiful? Well, we can not only eliminate the special casing, which is beautiful on its own, but we can rephrase each iteration in terms of a selection criteria generated by that equality check! We are never special casing; the reason we stopped was always because the selection criteria was the empty set. We just didn't think of it that way, because we didn't phrase the update step in terms of the generation of a selection criteria for updates.

And when you do, suddenly it becomes obvious how to do certain parallelizations because your selection strategy tells you where to kick off another refinement iteration. And /locality/ in a dimensional space is determining where the updates get passed. I have this strange feeling that if we just keep pulling on this idea that we'll be able to eliminate the need for loops that await all cluster updates and instead express the computation in a massively parallel way that ends up taking advantage of the topological structure of the problem: I mean, clearly if you have two clusters that moved one at 5 and another at at 900900 you don't /need/ to wait for 5 to finish its refinement to know that it /isn't/ going to impact the next step for refinement at 900900, because there are so many clusters between them. So you should be able to proceed as if 5 cluster movement has no impact on 900900 cluster movement. Only if they drift closer and the topology differs do you have to backtrack, but since we already need to pass these updates through the topological structure we have a fairly straightforward way of declaring when it is appropriate to backtrack. This phrasing is really stupid for the toy problems that people solve in classrooms and when trying to understand things because of the overhead of keeping track of the work and the wasted work, but I have a feeling that it might be practical. In real massive problems you already have to pay the cost of keeping the work because stuff fails and you need to retry and in particular the geometric probability distrubition of failure is high enough that we just have to assume that stuff fails in these massive cases. So the added cost of keeping the work around during the computation isn't as extreme a barrier. It's basically optimistic massively parallelized clustering, but with a resolution protocol for how to handle two optimistic clustering runs which collide with each other, because the natural problem of scale forces redundancy on us effectively making the choice to be redundant free rather than expensive wasted work.

Maybe nothing will come of these thoughts, but I found the first thought pretty and it provoked the second line of reasoning, which I found interesting. I'm working on a k-means clustering system that incorporates the good ideas from several k means research papers and I plan to explore these ideas in my implementation, but in the spirit of not hiding beautiful things, I hope you enjoy.

Also, as an aside, these aren't completely new ideas. People have noticed that you can use the triangle inequality to speed up computation for a while and shown it to speed up computations. It's more of an observation of the way the looping structure can be seen in a non-special cased way, how that suggests ways to improve performance, and how it lends itself better to alternative control flow structures.

> it's selfish to keep beautiful discoveries a secret.

It would be really fun to read what others found beautiful that they've never heard someone else mention.

I think we naturally want to share what we find beautiful as it is an expression of our joy as well as it enhances it. What we usually don't want to share is what we think will be profitable.

Learning that Knuth also has a mathematical background, I wonder what founders and great contributors to Computer Science don't have a mathematical background.

A lot of drivel here from old Knuth “Be original” “Happiness is not constant” “Find solutions to problems” “Humanize the thing to figure it out” Am I missing something here with ole Knuth?

damn, is he not dead yet?

>In Christian churches I am least impressed by a sermon that talks about how marvelous heaven is going to be at the end. To me that's not the message of Christianity. The message is about how to live now, not that we should live in some particular way because there's going to be pie in the sky some day. The end means almost nothing to me. I am glad it's there, but I don't see it as much of a motivating force, if any. I mean, it's the journey that's important.

I find this quite sad. In the US, I have never known a kind Christianity that espoused these ideas. The end, either heaven or hell (or purgatory), is everything to Christianity in the US, in my experience. Perhaps it used to be different here.

Depends on what flavor of Christianity you adhere to. I follow the Catholic mystical tradition which doesn't really focus on pie in the sky, but rather on the purpose of being, which is to become one with the divine-- a purpose which doesn't have to wait for the afterlife.

Came here to say this. One of the goals of a Christian life is to manifest heaven on Earth.

The interpretation that always interested me was that, when speaking of heaven, Jesus was referring to an enlightened state of mind and way of living here on earth, not some magical place you go when you die. It's obvious to anyone that you can create hell on earth without much effort; I like to think we can create heaven as well.

> The end, either heaven or hell (or purgatory), is everything to Christianity in the US

Yes, unfortunately this is the case in the dominant US expression of Christianity, Evangelicalism. But I think it's changing in some quarters. I've heard several sermons lately about how "eternal life" starts right here on earth. Check out The Bible Project's video on the meaning of Eternal Life [1]

I think The Bible Project is kind of on the vanguard of this movement within Evangelicalism (I think they're still theologically Evangelical, but maybe they'd shy away from using the term now since it's become loaded with political baggage), I wouldn't necessarily call it "progressive" but it's looking deeply into biblical interpretation and subtly calling out the predominate Evangelical interpretations.

Also, Check out NT Wright's "Surprised by Hope". He's coming from an Anglican perspective with an eschatology that predates the Evangelical "Left Behind" narrative.

[1] https://www.youtube.com/watch?v=uCOycIMyJZM

In evangelical Christianity, there is also the Red Letter Christians movement https://www.redletterchristians.org which is very much a minority movement, but that I would hope is growing.¹

⸻

1. I say this, though as an outsider, being a Catholic. We Catholics have our own battles between those who would make Catholicism all about sex and those who think that maybe it should be concerned with a bit more than that.

This looks more like political agitprop and a rehash of the social gospel movement of the early 20th century than a serious biblical exegesis.

> serious biblical exegesis

We (Christians) need this desperately in this day and age.

It's hard to say whether these movements (Like Redletter Christians) still consider themselves Evangelical - at least in the current sense of the word. There's a huge movement of (mostly younger) people leaving Evangelicalism right now because the term 'Evangelical' has been co-opted to mean something political rather than a theological category (as it was in the past). At the same time there are people who wouldn't have considered themselves religious in the past who are now identifying as 'Evangelical' more for political reasons. These latter folks may never attend a church but they like the political alignment.

Historically, Evangelicalism was a reaction to Fundamentalism in the early part of the 20th century. I'm old enough to remember that there were Evangelicals who were politically liberal - my parents voted for McGovern in '72 and were very much anti-Nixon, antiwar, pro-environment and pro-civilrights, they considered themselves Evangelical in those times and they weren't alone - these are the folks that helped Jimmy Carter win in '76. Now Fundamentalism and rightwing politics have taken over Evangelicalism. Leading to the exodus away from Evangelicalism in many quarters (though many of them would still consider themselves 'Evangelical' in the earlier theological sense, they feel that the term has been co-opted so that it's not so much that they've moved it's that the wider Evangelical church has moved away from it's original moorings).

I can say that I know of communities (and am part of one) of Christians in the US who view the journey here and now as vital. If you're interested, consider the book 'We Make the Road by Walking', McLaren, or the BEMA Discipleship podcast, being sure to start with episode 0.

Why should the journey be orthogonal to the destination? The Bible confirms that both are vital.

The Sermon on the Mount commands Christians to be kind, loving and good people in this life.

Verses like Matthew 6:19-21, Colossians 3:2 and 1 Corinthians 2:9 compel Christians to live this life in light of eternity.

To me, if you accept the presuppositions of the Christian worldview, this is logical. If this life and how you live in it is important, how much more so is eternity? After all, life is temporal. (Mark 8:36)

> That's not the message of Christianity > The end means almost nothing to me.

This betrays a fundamental lack of understanding of the Bible. Again, the Bible presupposes the existence of an eternal Heaven and an eternal Hell. This life is the seedtime for eternity.

I'm not here to argue with non-Christians about the validity of these pre-suppositions. I'm saying for those who call themselves Christian and therefore hold the Bible to be true, the end (should) means everything to them.

Growing up in the Lutheran church I found that unfortunately a lot of people didn't really read the Bible or think too hard about a lot of the passages. Most people listened to the sermons and how the pastor (or if you were in Lutheran day school like me, your teachers) interpreted and emphasized things. And while they did emphasize being a good person today, there was a huge emphasis on heaven and hell.

I think one of the results of what you describe is a subtle forsaking or compromise of fundamental Biblical truths in lieu of less controversial and more attractive principles that conform more closely with human sentiment and societal norms.

"the Bible presupposes the existence of an eternal Heaven and an eternal Hell." Not to turn this into a theology debate, but the Old Testament says next to nothing about either, and the New Testament doesn't spend much time on them, with maybe the exception of the book of Revelation. Otoh, you did say "presupposes", so possibly that's true.

> The Bible confirms that both are vital.

Evangelicals just as easily claim the opposite, on the same conceit. "The Bible says". If this wasn't up to interpretation you wouldn't have so many protestant sects.

For instance, being kind and loving could be construed as an obligation for Salvation, not a reflection of the importance of Earth life. There are a not-insignificant number that oppose utilitarian improvements to quality of life because it might "distract people from God", notwithstanding how comfortable their own lot might be. It's not at all life-affirming for them, at least not in terms of how they feel of their neighbors.

> being kind and loving could be construed as an obligation for Salvation

It certainly can be and has been construed in this way and a proper exegesis of the New Testament has no other conclusion than that interpretation is patently wrong.

The book of Galatians (amongst) others is a clear rebuke of the heresy of salvation by works.

Those who oppose utilitarian improvements to quality of life ignore verses such as

"Do not neglect to do good and to share what you have, for such sacrifices are pleasing to God."

"So whatever you wish that others would do to you, do also to them, for this is the Law and the Prophets."

"Let each of you look not only to his own interests, but also to the interests of others."

"Whoever is generous to the poor lends to the Lord, and he will repay him for his deed."

"Give to the one who begs from you, and do not refuse the one who would borrow from you."

"But love your enemies, and do good, and lend, expecting nothing in return"

The term "good Samaritan" comes from a Biblical parable highlighting the importance of being kind to others.

I don't how anyone can come away from a serious and accurate study of the Bible and not conclude that a Christian's conduct in this life is wholly important.

> sad. In the US, I have never known a kind Christianity that espoused these ideas.

And for contrast, I’ve never participated in an american church that has espoused anything but, and haven’t found that aspect of the faith to be particularly difficult in meeting.

I know that the “pie in the sky” churches are out there, i just don’t attend them.

I used to use the term "evangelical" to describe myself, but given the usage of that term in the last ten or so years, I've stopped, and I just consider myself a Christian.

That's a preface to what I really wanted to say, which is that having been in various kinds of evangelical-like churches for the past 50 or so years, and having heard a lot of sermons both good and bad (and by "bad" I mainly mean boring, only occasionally something wrong), I've never heard much about heaven or hell; in fact, I can think of precisely one sermon that really gave the topic of heaven much thought, and none that talked about hell. I'm at a loss to explain why your experience and mine are so different.

BTW, if you've read C.S. Lewis's Voyage of the Dawn Treader, I have always thought that the monopods (duffers) were a congregation, and their chief a pastor who is constantly preaching boringly obvious things: "And what I say is, when chaps are visible, why, they can see one another." And such like.

I recommend the Don Camillo stories from G. Guareschi.

It's kind of a balm for when I feel particularly atheist and annoyed at the world at large.

>In the US, I have never known a kind Christianity that espoused these ideas. The end, either heaven or hell (or purgatory), is everything to Christianity in the US, in my experience. Perhaps it used to be different here.

In the Orthodox Church, which I am member of, the accent is on the journey and on the transforming of the individual, not on the prize/punishment.

I live in Eastern Europe, but there are orthodox churches in US, like the Orthodox Church in America. You can go and visit at one, and see what's about. You can also chat with a priest or a monk while there.

I think that while most protestant, neo-protestant, episcopalian and even catholic churches steadily diluted the religion, the orthodox church try to stay true to the same initial truths the same ways as thousands of years ago.

I admire Donald Knuth for his contribution on algorithms and CS stuff. He is one of greatest computer scientist of our time. But would his every advice outside CS fields will be great? I am not sure about this.

Moreover: "Is his advice outside CS great _for me_?"

He's exceptional, in a very literal sense, so your prior would have be be 'no'

Do you require advice to be great before you listen to it? I tend to decide whether advice was great after I've heard it, or better still after I've put it into action.

Anyone who achieves on his level possesses not just raw innate brainpower but also other skills, for example organizational skills.

Don't you think well accomplished people are qualified to talk about problem solving and work habits? Seems those skills would be necessary for their achievements.

(2020)

>That's quite different from a bachelor's degree or a master's degree; those degrees are awarded for a mastery of existing knowledge

I didn't know a BsC was a sign of mastery of a field.

How did you get from "mastery of knowledge" to "mastery of a field"?

Knuth is a failed Mathematician. He basically couldn't solve the problem Manin gave him so he escaped to a beach. I don't think his guidance matters that much. I'll listen to him only when he has the solution.

Interesting. Which problem did Manin give him? How do you know all this stuff?

Reply on news.ycombinator.com