Hacker News Reader

Comment by zero_k | Hacker News Reader

I was involved with implementing the DNF volume counting version of this with the authors. You can see my blog post of it here:

https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...

And the code here: https://github.com/meelgroup/pepin

Often, 30% of the time is spent in IO of reading the file, that's how incredibly fast this algorithm is. Crazy stuff.

BTW, Knuth contributed to the algo, Knuths' notes: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf

He actually took time off (a whole month) from TAOCP to do this. Also, he is exactly as crazy good as you'd imagine. Just mind-blowing.

View on HN

That’s really interesting and thanks for sharing.

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.

I feel extremely jealous of you.

You are envious of him.

Jealous is when you possess something you don’t want taken away by someone else

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.

In most other domains, though, like this one, jealousy and envy are synonyms. https://www.merriam-webster.com/dictionary/jealousy#did-you-...

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.)

> 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.

Experience and age have diminishing returns.

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.

He’s barely able to read a teleprompter, not too confident that Biden himself enacted those changes.

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.

> We've had nearly 4 years with no scandals

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.

Hello inflation.

>> and gun control bills

> 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.

> Eschew flamebait. Avoid generic tangents.

https://news.ycombinator.com/newsguidelines.html

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.

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

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.

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.

> 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.

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:

https://www.sciencedirect.com/science/article/pii/0022000078...

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.

does that mean you could also split the set in half multiple times then run it on each half of a half (etc) and combine it with its other half?

that would seem simpler to me.

edit: oh but then you would need to keep the results which defeats the purpose

You would need to assume a uniform distribution of items, which I don’t think this does

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.

What are the main applications of this?

So now we have you to blame for a delay on the release of his next book. :)

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 agree with zero_k on everything he said about Knuth and strongly disagree with his own (extremely modest) characterization of himself.

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.

Reply on news.ycombinator.com