Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithm No One Knows About (2016)

getkerf.wordpress.com

Post reply on HN
Print view View original

171–180 of 200 posts

Re: Algorithm No One Knows About (2016)

#171

Post by interfixus »

ghusbands wrote: post #61

The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.

This is my homespun solution whenever I need a deterministic, non-repaeting mapping of a sequence. Except I rely - shame on me - on a variable blocksize encryption scheme I've hacked together for just this purpose.

Output - of the mapping as well as of anything I run through the encryption algo - passes all pseudo-random validity testing I throw at it, but obviously I would never, ever consider using the thing where real security was a concern.

Re: Algorithm No One Knows About (2016)

#172

Post by theelous3 »

dmurray wrote: post #167
debatem1 wrote: post #153

Earlier quoted context omitted.

O(1) /extra/ space, but we must have working space at least the size of the output.

The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.

The number of values you've seen could be "only" an exabyte, which is a problem.

Re: Algorithm No One Knows About (2016)

#173

Post by dahart »

ghusbands wrote: post #61

The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.

This is a good way to pick a few 64 bit numbers without duplicates, if 64 bit numbers is what you need.

I didn't see any replies to you mention this part, but Vitter's algorithm works on an unknown number of samples. You can pick a 64-bit number uniformly when you know in advance you have exactly 2^64 choices. But how would you pick samples from a stream with equal probability, without knowing how many items are in the stream? Maybe it's 3, maybe it's 2.493e85, you won't know until you run out, and when you do, you want to have picked some items from the stream with uniform probability.

Re: Algorithm No One Knows About (2016)

#174

Post by nomadictype »

eyegor wrote: post #43

Does anyone have a mirror for this? No matter what I do, all I'm getting is an empty page with a sidebar.

In Firefox: View -> Page Style -> No Style

(For whatever reason the page has a CSS rule #content { display: none; }, which presumably gets removed via JS.)

Re: Algorithm No One Knows About (2016)

#175

Post by Someone »

saagarjha wrote: post #135
Someone wrote: post #126

”Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication. […] Stated more formally: given non-negative integers k and n with k , generate a list of k distinct random numbers, each less than n .“ I think that knowing k beforehand makes it a different, easier problem. I don’t see how, if you don’t know k beforehand, you can do without enough memory to store a…

I don't see why you'd need to generate a permutation?

If you don’t know k beforehand, you have to (eventually) handle the case where k is large, possibly even equal to n.

If it turns out to be equal to n, you have to generate a permutation.

If it isn’t, you don’t need to, but you need to keep enough information around, in case it turns out that you need.

For example, by the time you’ve generated 2⁶³ integers in the range 1…2⁶⁴, you need to know which 2⁶³ integers still are ‘available’.

I think you can’t do that more compactly than by just picking the permutation to generate at start (whether you can efficiently determine the k-th number in that permutation is a separate problem)

Re: Algorithm No One Knows About (2016)

#176

Post by yati »

dahart wrote: post #169

It’s called Reservoir Sampling https://en.wikipedia.org/wiki/Reservoir_sampling I was just re-reading this yesterday! I think a lot of the Monte Carlo rendering people know about this family of algorithms, and the idea is pretty simple. I’m not sure why it’s described from the start as picking k samples though, I find it a lot easier to understand and see how it works when you start with k=1. Btw, it’s fun to work ou…

Reservoir sampling requires you to maintain a reservoir of n items that will be your sample. This can be prohibitive if the sample size itself is huge. The algorithm described here decides (commits) whether an item is to be sampled as it sees it (i.e., online), while consuming a constant amount of memory. It differs from the usual reservoir sampling approach in that it cannot go back and "unsample" an item it already selected (whereas the crux of a reservoir sampling approach is evicting current candidate items and replacing them with new items).

Re: Algorithm No One Knows About (2016)

#177

Post by thaumasiotes »

the8472 wrote: post #107
norswap wrote: post #81

Earlier quoted context omitted.

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking . That might be just 10.

As a sibling comment mentions the constraints given simply don't allow sampling with rejection due to the memory constraints. You get a stream of uniform samples, you're not allowed to store them. But even if you were allowed to store them the algorithm still has an advantage. It doesn't require random access, only sequential reading and skipping. This was made for tapes, but is also useful for cases where it's simpl…

> even if you were allowed to store them the algorithm still has an advantage. It doesn't require random access, only sequential reading and skipping. This was made for tapes, but is also useful for cases where it's simpler or more efficient to stream your data source instead of doing random access.

This is a good point, but its evil twin is the point that this algorithm requires you to read the entire data set, every time, making it undesirable for any application where you can do random access.

Re: Algorithm No One Knows About (2016)

#178

Post by thaumasiotes »

theelous3 wrote: post #172
dmurray wrote: post #167

Earlier quoted context omitted.

The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.

The number of values you've seen could be "only" an exabyte, which is a problem.

You're storing the number of values you've seen:

    So far, I've seen 172 values.
You're not storing the values themselves. If the number of values you've processed is too large to fit in memory... you probably had to spend a long, long time processing those values. It's not a relevant objection.

Re: Algorithm No One Knows About (2016)

#179

Post by tripzilch »

> When I came across a need for the algorithm in my work, it took a lot of detective work to even find it. There was no source code online. The algorithm is not referenced often, and when it is, it is in a highly obscure fashion.

Well, the author certainly isn't helping that problem with a clickbait title like that, and being all mysterious for the first few paragraphs, teasing "you almost certainly don't know this".

"Dealing cards from an extremely large deck: Vitter's Algorithm"

Except he doesn't even explain the algorithm, just some source code (which is super unclear, no comments, short variables). And the unhelpful comment that it was hard to figure out from the paper. All the reason to put a more descriptive title.

How does he expect to help people find this, figure this out, or was this entire post just to brag that "his" solution is better than anyone else's because he found the right algorithm almost nobody else knows about?

Re: Algorithm No One Knows About (2016)

#180

Post by tripzilch »

ZephyrP wrote: post #143
OscarCunningham wrote: post #58

Earlier quoted context omitted.

Is there an easy way to adapt the algorithm to get the cards drawn in a random order? The article says "it’s easy to randomize the order after the fact" but if we can't store them in memory then that's a no-go.

You can draw the cards in a random order by using the output of an accumulator fed to a block cipher as an index. The fixed output size of a block cipher does entail extra work in filtering numbers outside the range you'd like, just as you would with an LFSR. (as a direct power of 2, you could directly use an LFSR or some ECB-mode block ciphers as if it were format-preserving, but that is "coincidence"). You can prod…

Is that code correct? Why do you overwrite `result` every step of the loop if you only use it at the end?
Post reply on HN