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

101–110 of 200 posts

Re: Algorithm No One Knows About (2016)

#101

Post by LolWolf »

dahfizz wrote: post #93
LolWolf wrote: post #71

Earlier quoted context omitted.

In general, assuming that we have constant-time operations on arbitrarily large numbers (which we almost universally assume when doing these analyses, except in very specific fields), then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Additionally, the only problem with this approach is the extra O(k) space taken up by…

> then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Hashtables can never guarantee constant time operations. It is expected O(1) time, but it is completely possible that everything hashes to the same bucket and you get O(n) operations, no matter how much you rehash.

The algorithm is a randomized algorithm and we're assuming we're picking a good hash. The probability of that event is exponentially vanishing, so, in expectation (which is the runtime we're looking for, as we are analyzing a randomized algorithm based on rejection sampling) it is O(1).

In the worst case analysis of this rejection-sampling algorithm, the time for table look up and insertion doesn't even factor in since you'll have infinite run-time.

Re: Algorithm No One Knows About (2016)

#102

Post by SilasX »

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.

Wait, are symmetric ciphers guaranteed to cycle through the full space of block-sized numbers when applied to their output like that? I thought that was just "close to" true?

Re: Algorithm No One Knows About (2016)

#103

Post by wysifnwyg »

natch wrote: post #97

Some of the variable names used: i, j, t, qu1, S, n, N, U, X, y1, y2, V I know others have already commented on this but I think it's worth laying out all of the cryptic variables and asking: are some of these shorthand for well known math concepts that make it unnecessary to have a more descriptive name? I understand the use of temporary value holders like `i`, but have no clue what some of the others might be used…

>are some of these shorthand for well known math concepts that make it unnecessary to have a more descriptive name?

With context, I would agree that it's unnecessary to have a more descriptive name. N is the population, n is a sample in the population. However, without the context and experience which makes these values recognizable, they're exceptionally unhelpful.

Re: Algorithm No One Knows About (2016)

#104

Post by [deleted] »

nemo1618 wrote: post #99
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 works, but only if you're sampling the exact same space as the block size. For example, if your cipher outputs 64-bit blocks, but you want to sample in 2^32, you're back to the drawing board, because there's no way to truncate the cipher output without risking duplicates.

[deleted]

Re: Algorithm No One Knows About (2016)

#105

Post by ghusbands »

SilasX wrote: post #102
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.

Wait, are symmetric ciphers guaranteed to cycle through the full space of block-sized numbers when applied to their output like that? I thought that was just "close to" true?

Yes, it's bijective. For every input value, it provides a unique output that will decrypt back to that input.

You might be misunderstanding the algorithm. We're only encrypting an incrementing number, not ever encrypting something that is already encrypted.

Re: Algorithm No One Knows About (2016)

#107

Post by the8472 »

norswap wrote: post #81
drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

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 simpler or more efficient to stream your data source instead of doing random access.

And of course it also works for m < k < n, where m is your memory size. E.g. when you're performing analysis on a dataset with 10^12 entries, you only want to sample 10^9 of them and don't have the storage (or don't want to pay the IO overhead) for either.

Re: Algorithm No One Knows About (2016)

#108

Post by the8472 »

nemo1618 wrote: post #99
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 works, but only if you're sampling the exact same space as the block size. For example, if your cipher outputs 64-bit blocks, but you want to sample in 2^32, you're back to the drawing board, because there's no way to truncate the cipher output without risking duplicates.

A variable-size block construction would help here. It doesn't even have to be cryptographically secure, only bijective and statistically good enough similar to PRNGs sans CS. It doesn't even have to be keyed.

Re: Algorithm No One Knows About (2016)

#109

Post by SilasX »

ghusbands wrote: post #105
SilasX wrote: post #102

Earlier quoted context omitted.

Wait, are symmetric ciphers guaranteed to cycle through the full space of block-sized numbers when applied to their output like that? I thought that was just "close to" true?

Yes, it's bijective. For every input value, it provides a unique output that will decrypt back to that input. You might be misunderstanding the algorithm. We're only encrypting an incrementing number, not ever encrypting something that is already encrypted.

Ah, okay. Thanks! Maybe I was thinking of hash functions, for which it's not guaranteed that every output has an (n-sized) pre-image?

Edit: To clarify, I do now understand that you were proposing:

random number X -> output encrypt(X), encrypt(X+1), encrypt(X+2), etc

Which I had misinterpreted as:

random number X -> output encrypt(X), encrypt(encrypt(X)), encrypt(encrypt(encrypt(X))) etc.

Re: Algorithm No One Knows About (2016)

#110

Post by supergarfield »

web007 wrote: post #79
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 select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.

I understand "you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them" as "N cards don't fit in memory". Or is the relevant distinction memory vs disk, as it's feasible to randomize on-disk data?
Post reply on HN