Algorithm No One Knows About (2016)

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 if they're hidden in…

> The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. If you draw (with replacement) over and over again, ignoring cards you’ve already picked, you can simulate a deal, but you run into problems. The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem). I don't think this is true! First note that if you want to pick…

The article mentions the challenges of working with a deck of 2^64 cards, but I don't see how the algorithm helps - seems like it's going to encounter the limits of double-precision values well before that. For instance, the initial setup of "qu1real": qu1real = -nreal + 1.0 + Nreal will behave poorly if N > 2^52 or so. The cited paper refers to this in the Appendix, mentioning that "Roughly log10(N) + 1 digits of precision will suffice", so…