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

141–150 of 200 posts

Re: Algorithm No One Knows About (2016)

#141

Post by HelloNurse »

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?

Counter mode means encrypting successive (all different) numbers, not the previous output. There is no issue with cycles.

Re: Algorithm No One Knows About (2016)

#142

Post by SilasX »

HelloNurse wrote: post #141
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?

Counter mode means encrypting successive (all different) numbers, not the previous output. There is no issue with cycles.

Yes, the original commenter replied to say that and I agreed to it.

https://news.ycombinator.com/item?id=20962758

Re: Algorithm No One Knows About (2016)

#143

Post by ZephyrP »

OscarCunningham wrote: post #58
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…

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 produce an exact random permutation with a Feistel network for any number, in this case selecting every number between 0 and 2^64 exactly once, with no appreciable space requirements.

   procedure feistel(input) {
      result = input;
      h = 2

Re: Algorithm No One Knows About (2016)

#144

Post by twic »

CobrastanJorji wrote: post #133
twic wrote: post #112

Earlier quoted context omitted.

You can use the "hasty pudding trick" to truncate the cipher output without risking duplicates. It is inefficient if the block space of the cipher is much larger than the sampling space, though. However, you can also use a Feistel network to create a block cipher for an arbitrary bit length. So, you can always bound the block space to be no more than twice the sampling space, which is okay.

What's the hasty pudding trick? Is it related to the Hasty Pudding cipher?

It is. Perhaps it's not officially called that, but that's how it was described to me:

https://groups.google.com/d/msg/sci.crypt/gjYclOVJDrc/tiv4ic...

Re: Algorithm No One Knows About (2016)

#145

Post by dahfizz »

inlined wrote: post #115
dahfizz wrote: post #93

Earlier quoted context omitted.

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

> Hashtables can never guarantee constant time operations. A bit mask is a form of hash table and is guaranteed O(1) lookup for O(lg(Universe)) space. When you have fixed universes, all kinds of options open up. I personally love vEB Trees, which can do set operations in O(lg(lg(U)))

Yes, in cases where direct addressing is possible you get guaranteed constant time. That's really more of an array than a hashtable IMO.

Re: Algorithm No One Knows About (2016)

#146

Post by drfuchs »

aidenn0 wrote: post #127
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…

If you can store 2^64 data points, why cant you store 2^63 indexes? That's a very small increase in memory requirements.

The issue isn't storage requirements; the issue is that, in the environments where this algorithm is useful, random access to the storage device is orders of magnitude slower than sequential access. Think magnetic tape in 1986, or today's spinning rust hard drives that take relatively forever to "seek", or even RAM being accessed sequentially, allowing the CPU to speculatively pre-fetch cache lines in burst-mode.

Using Vitter's algorithm for generating the random numbers in order, one at a time, lets you do a single, serial pass through the 2^64 records on said device, streaming out the selected records sequentially.

If instead you generate your 2^63 random numbers out of order, you'll have to do at least 2^63 random writes one way or another. Even if you have an extra exabyte to do these writes into (and don't mind waiting to generate all 2^63 of them before outputting the first one), it will take a prohibitively long time to do, since it's not sequential writing.

That's the motivation behind this algorithm; if the characteristics of your exabyte-scale storage device are not "sequential = fast / random = orders-of-magnitude-slower", then it may not be of interest.

Re: Algorithm No One Knows About (2016)

#147

Post by hinkley »

OscarCunningham wrote: post #58
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…

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.

There are kinds of PRNGs that are designed to emit every possible ouput value in the range. There are some that will emit every possible value before a repeat.

If you look at his code, the first function seems to be calling a method that claims to do the latter. I think his documentation may be out of sync.

Re: Algorithm No One Knows About (2016)

#148

Post by hinkley »

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…

Yes but, I feel like he's still working too hard.

I've 'reinvented' an algorithm at least twice to generate/iterate all permutations or combinations of a list by counting from 1 to P(n, k) or C(n, k) and just doing repeated divisions to determine the next element in the sequence. That generates them in order. If n is small enough to fit into memory then you can shuffle the inputs, but that still gives you a partially ordered output (all outputs with 'foo' in the same position are contiguous, for instance).

I always left myself a TODO to use a PRNG instead of an increment if I needed the outputs to be more shuffled than that, but it never got that far.

Re: Algorithm No One Knows About (2016)

#149

Post by [deleted] »

stillworks wrote: post #82
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.

From the article: "Stated more formally: given non-negative integers k and n with k Focus on k Also, in the comments section in the article, the author counters a comment in favor of Python's random generator along the same lines.

[deleted]

Re: Algorithm No One Knows About (2016)

#150

Post by andreareina »

petters wrote: post #53
andreareina wrote: post #14

Earlier quoted context omitted.

Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.

You're right, but it's not 2^8. It is √2^64 = 2^32.

Yes, thanks. Took the root of the wrong number.
Post reply on HN