Proofs and proof checking is also big in SAT solving (think: MiniSat) and SMT (think: z3, cvc5). It's also coming to model counting (counting the number of solutions). In fact, we did one in Isabelle for an approximate model counter [1], that provides probabilistically approximate count (a so-called PAC guarantee), which is a lot harder to do, due to the probabilistic nature.
I am very curious about the extraordinarily gifted. What made you think Knuth is crazy good? Was there a particularly moment? Was it how fast he groked ideas? Was it his ability to ELI5?
What made me realize is that I saw some snippets of emails he wrote to a colleague. It was... insane. You could see his mind race. He recognized patterns in minutes that would take me days, if not weeks, to recognize. Also, he actually writes and runs code, overnight if need be. It was as bit of a shock to me. He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.
> He recognized patterns in minutes that would take me days, if not weeks, to recognize... he actually writes and runs code, overnight if need be
70-80 years of actually being hands-on and i bet you'd be pretty quick too. dude is definitely naturally "gifted" but it seems pretty obvious being hands-on has a lot to do with it.
Disagree, there are thousands of highly experienced and hard-working computer scientists. If we grant that very few of them are the equivalent of Knuth, there must be something else at play.
Most computer scientists I know at that age don’t touch a computer any more and hang with grand kids. That’s not a value judgement - Knuth is impressive but as a human being most people choose their humanity over their careers in some way. Beyond being simply smart and productive knuth is also likely obsessive about his work and his life is warped around it. As long as that works for everyone that’s great. But most people don’t live that life.
> Most computer scientists I know at that age don’t touch a computer any more and hang with grand kids.
That doesn't sound right to me at all. Modern academia is highly competitive, and career academics typically have long working hours.
If they aren't doing programming, that's likely because it isn't relevant to their job. A theoretical computer scientist is closer to a mathematician than to a typical programmer.
> Knuth is impressive but as a human being most people choose their humanity over their careers in some way
We're talking about scientists, not most people.
Getting a PhD is no cakewalk, and there are far more PhDs than faculty positions. You can try being a workaholic, but if your competitors are doing the same, that won't make you stand out.
> obsessive about his work and his life is warped around it
Again this describes every modern scientist. Deep knowledge of one's field, and deep commitment to it, are just table stakes.
This doesn’t describe post tenure academia. You seem to be describing the life of a young tenured track academic.
Additionally while Knuth is clearly an outlier by any measure he’s also an outlier in his celebrity. There are a lot Knuths out there who aren’t well known outside their specialty, or are in industry. He played a seminal role in a field everyone studies in computer science and published a uniquely interesting and continuously revised set of fundamental books in the field. However in my time in academics there were people in say transactional memory for speculative out of order compute whose work powers every machine in use today and they still contribute similarly powerful work. They’re obsessive and very driven by the problem space. But for everyone one of those in academia there are a hundred tenured professors who paper mill their undergrads (generously).
You mention long hours but I said obsessive. That’s orders of magnitude more than working hard. It’s so distorted as to be pathological if they weren’t paid and rewarded for it. Yes many academics are pathologically obsessive. But unless they are bringing in funding or repute to fill a deficit in the department, there’s no work for them in current academic settings.
Finally Knuth isn’t a common occurrence because -he doesn’t bring in money-. Modern academia is oriented towards grant milking. The example of the txn memory guy is interesting because he brings in lots of research funding from intel and ARM and NVidia because his work is very commercial. Knuth - not so much I imagine. He brings repute, but you can only find so much repute with modern academic funding models before they’re a net negative on the department. Knuth is a fossil of a different era in academics (not used as a pejorative).
> That doesn't sound right to me at all. Modern academia is highly competitive, and career academics typically have long working hours.
> If they aren't doing programming, that's likely because it isn't relevant to their job. A theoretical computer scientist is closer to a mathematician than to a typical programmer.
This kind of stuff is not useful to be posting where impressionable people (young students) can read it. The truth the majority of academics are managers and delegate hands-on work to postdocs and PhD students. I finished a PhD just last month and I never saw in 4 years anyone on my committee so much as look at code let alone write it (and I was not a theory student). Almost everyone in my cohort would echo this observation.
Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.
Actually quick is definitely something that comes to mind. Quick in politics is of course relative, but the speed with which he has enacted major changes (for example marijuana legalization) is pretty quick in the realm of politics when congress is of the other party.
We've had nearly 4 years with no scandals and emerged from the pandemic with the best economic recovery of any country, and despite having no margin to spare in Congress, master legislator Joe Biden has secured massive climate change, infrastructure, and gun control bills, not to mention he's ended our two decade war in Afghanistan and overseen the fastest wage growth of the two lowest income quintiles seen in modern history.
And every time people actually watch him speak (not just a selected clip), there's weeks of coverage about how alive JB seems, not recognizing that all evidence points to that being typical.
This isn't the flex you think it is. When the media is lapping out of your hand like a 6 week old puppy instead of doing their fifth estate job, of course there are no scandals.
> and gun control bills,
You mean stripping Americans of their constitutional rights.
> not to mention he's ended our two decade war in Afghanistan.
Which was an unmitigated disaster.
> and overseen the fastest wage growth of the two lowest income quintiles seen in modern history.
> You mean stripping Americans of their constitutional rights.
Not that I disagree with you, but when posters like modriano engage in political/partisan commentary on HN, I find it more productive to merely downvote and flag their comments rather than replying and getting engaged in a war.
A dead post makes quite the impression, as this sort of political commentary just generally defeats the quality of discourse on HN (which, you must admit, is much better than many other platforms, and I'd like to try to preserve it as long as possible).
> Biden's been hands-on in his domain for over 50 years, yet "quick" is definitely not the word that comes to most people's mind when they think of him nowadays.
Please don't post flamebaity political tangents on HN.
It’s a counterpoint anyone can identify with. One can interpret it uncharitably as flame bait if one wants to, but it need not be. It could have been Reagan in his second term, but some may not know who he was. Or Lee Smolin.
This is objectively false. It is not a counterpoint, because it's not an argument. It's an extremely subjective claim that is highly contentious (like jedberg's sibling comment[1]), definitely not something that "anyone can identify with" (as the vast majority of people do not know Joe Biden and instead view him through one of a small number of extremely skewed lenses) and clearly in the realm of "off-topic flamebait" that is not appropriate on HN.
I’d avoid the Reagan or other comparison as well even if I have medical evidence for their decline as you see with Reagan. In this specific case of Biden there’s not even that so it’s purely a political opinion and it’s definitely bait for flame even if not intended as such.
> Also, he actually writes and runs code, overnight if need be...He's not in an ivory tower. He's very much hands on, and when he's behind the wheel, you're in for a ride.
That's such an admirable thing. Something to aspire to, given his age. I wonder if one can say the same thing of all the 'thought leaders' of the industry who go around pontificating about code hygiene and tidiness.
Well, that use of jealousy is only really common in certain romantic situations. Like if some super good looking dude hits on your girl and she responds in an ambiguously-flirty way, you might definitely be said to be jealous, even though she didn't run off with him.
I read that link as supporting the distinction, not refuting it: "It is difficult to make the case, based on the evidence of usage that we have, [that they are] exact synonyms [or] totally different words."
An envious person would be happier having something that someone else also has. A jealous person feels threatened that someone else has or wants something. This distinction applies in romantic and non-romantic contexts. Both emotions can arise, for example, when someone observes someone else wanting something neither of them has, or when the thing wanted is inherently exclusive.
I don't lose a lot of sleep worrying about others' use or misuse of these words. But I do think it's essential for people to understand which of the two emotions they're having, because the solution really depends on that. Would I be happy if I destroyed that other kid's toy? (That's jealousy.) Would I be happy if my dad showed up and gave me a similar toy, so that the other kid and I could play together? (That's envy.)
This looks dumb....very dumb, am I missing something? This is not counting, its just sampling AND if you want to actually count all the distinct words the memory size used doesnt change in comparison to just counting.
Maybe you'd know, but why would one choose to not sort favoring larger counts and drop the bottom half when full? It may be obvious to others, but I'd be curious.
The guarantees would not hold, I'm pretty sure ;) Maybe one of the authors could chip in, but my hunch is that with that you could actually introduce arbitrarily large errors. The beauty of this algorithm really is its simplicity. Of course, simple is.. not always easy. This absolute masterpiece by Knuth should demonstrate this quite well:
It's an absolutely trivial algorithm. Its average-case analysis is ridiculously hard. Hence why I think this whole Ordo obsessions needs to be refined -- worst case complexity has often little to do with real-world behavior.
Worst case complexity matters when the input data can be manipulated by someone malicious, who can then intentionally engineer the degenerate worst case to happen - as we have seen historically in e.g. denial of service attacks exploiting common hash table implementations with bad worst case complexity.
No, you're throwing away a random selection of 50/50. You would have to flood the algorithm with uniques or commons to set the algoritm to a probability of a known state.
You want every distinct item to have the same chance at the end. So when items repeat you need to reduce (not increase) the odds of keeping any given occurrence.
Let’s prove it by contradiction:
Lets say you pick the larger ones and drop the smaller ones every single round, you have lost the probabilistic guarantee of 1/2^k that the authors show because the most frequent words will be the lost frequent in subsequent rounds as well. This is the intuition, the math might be more illuminating.
Not me, the authors -- I'm a fly on the wall compared to them ;) This is some serious work, I just did a fast implementation. Re implementation -- it turns out that there are parts of some standard libraries that this problem pushes to its limits, that we had to go around during implementation. So there were still some cool challenges involved. I was also pretty happy about the late binding/lazy evaluation thing I came up with. Of course Knuth just did it (check his notes), without even thinking about it :D What is an achievement for me is a lazy Monday coffee for him, but oh well!
I am pretty confident that this was not the only problem/algorithm that "distracted" Knuth during the years. You can see that whenever he encounters interesting issues he has no problem pausing the work on TAOCP and pursue other goals.
I am 100% with you. I have infinite admiration for von Neumann's talents. He was the genius of the geniuses. I wish I could have a 10 minute chat with him. He'd blow my mind, I'm sure. I'd love to explain some of the research issues I'm working on to him, I have a feeling he'd nail them to the ground. His resume is absolutely insane. The dude invented merge sort and it's an effin' side-note to his work. Like, WAT. His achievements could fill the resume of 50 Nobel Laureate scientists. Plus apparently he had a CHARACTER, like a real one. Would have loved to shoot the sh&t with him.
There were others in his league who have been mostly lost in history. When von Neumann first published a description of a stored-program binary computing machine in 1945, he cited only one paper -- which was co-authored by Walter Pitts;
It's trivial in an era where the concept of algorithms is established but less so back in the 1940s. You really had to be at the forefront to know that sorting algorithms are meaningful things to think about. But indeed mergesort is really not even a footnote of von Neuamnn's contributions to computing, which was perhaps not even 1/3 if his career. That's how much a giant he was.
People have done merge sort, insertion sort, etc., by hand, for a very long time, probably centuries, and re-invented by many people. I would be very surprised if the steps had not been written down earlier. Algorithms done by hand, e.g. numerical methods, have been around for centuries too, so it's not that the concept was missing.
The big advantage of electronic machines was speed. Early* digital computers didn't have much more memory than the card processors (64-128 bytes), but they weren't limited to cards/minute.
I get you. It took me a looong time to come to terms with the fact that I can buy myself some nice things, even though I was already gifting nice things to others. I still only rarely buy nice stuff for myself, but I am learning. I bought myself a high-end computer (5950x & RTX 3070) 3 years ago, and I realized how important it is to spend -- it's sometimes cheaper than buying it later (it was the beginning of the silicon crisis), and you get to enjoy it a lot. I still pay a lot of attention to what I buy and for what purpose, but I am less crazy about not spending it.
It takes actual time to learn to spend, and you gotta be patient with yourself.
I read that many (10? 15?) years ago and it changed me. It literally, changed me. That blog post, and its comments (including one by the sister of the author... really difficult stuff) is incredibly hard and important to read.
Indeed. If you wanna understand this more in-depth, I suggest the book "Can't Catch a Break: Gender, Jail, Drugs, and the Limits of Personal Responsibility". It does exactly what it says on the lid, an amazing book.
[1] https://github.com/meelgroup/approxmc