Computer Scientists Invent an Efficient New Way to Count

Re:Computer Scientists Invent an Efficient New Way to Count by cb321 on Friday May 17, 2024 @08:36AM (#40389210)

I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1]

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

[ Parent | on HN ]

Re:Computer Scientists Invent an Efficient New Way to Count by imglorp on Friday May 17, 2024 @09:48AM (#40389828)

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation.

    X ← X \ {ai}

[ Parent | on HN ]

Re:Computer Scientists Invent an Efficient New Way to Count by jtanderson on Friday May 17, 2024 @09:59AM (#40389984)

That is conventional set subtraction notation. "Assign to X the same set minus all elements of the set {a_i}".

One example source, but it is pretty common in general: http://www.mathwords.com/s/set_subtraction.htm

[ Parent | on HN ]

Re:Computer Scientists Invent an Efficient New Way to Count by rocqua on Friday May 17, 2024 @10:02AM (#40390021)

Set difference.

Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.

[ Parent | on HN ]

Re:Computer Scientists Invent an Efficient New Way to Count by _a_a_a_ on Friday May 17, 2024 @12:49PM (#40391821)

I've known that symbol for decades, never knew it's name - up-tack it is. Ta!

[ Parent | on HN ]

Re:Computer Scientists Invent an Efficient New Way to Count by kuldeepmeel on Saturday May 18, 2024 @02:48PM (#40401092)

You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct).

It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.

[ Parent | on HN ]