Algorithm No One Knows About (2016)

Post by saagarjha » Fri, Sep 13, 2019, 4:46 PM UTC

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.

Post by CobrastanJorji » Fri, Sep 13, 2019, 4:50 PM UTC

twic wrote: post #112

nemo1618 wrote: post #99

Earlier quoted context omitted.

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.

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.

Post by saagarjha » Fri, Sep 13, 2019, 4:54 PM UTC

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…

Post by SamBam » Fri, Sep 13, 2019, 5:07 PM UTC

kadoban wrote: post #63

mihaifm wrote: post #54

Earlier quoted context omitted.

That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).

The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k. If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results imme…

Post by pmiller2 » Fri, Sep 13, 2019, 6:05 PM UTC