91–100 of 200 posts
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.
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.
you can also use a Lehmer random number generator of full period.
Earlier quoted context omitted.
No structure can check membership in O(1) time if n is big enough.
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…
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 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.
I’ve used this trick with a 64-bit block cipher (base-32 encoding the result) to generate short, unique public identifiers (to put in URLs) for entries in a database based on an integer primary key.
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.
Okay, so this is a way to generate a sampling in order, so you don't have to keep a sorted list and your run time can be k instead of klogk. Mostly. The body of the post, with its talk of strict timing and sample bias, had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n. If this algorithm hi…
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 for or what the single letter names indicate.
Another way to ask the question: if the author had just used instead a, b, c, d, e, f, g, h, etc. what information would be lost, that is gained by the particular letter choices that were used? This isn't rhetorical, although there is a point to be made for sure about clarity in naming... I'm really wondering if anyone can explain what these letters might mean if you are more versed in the math than I am.
BTW here's another Vitter paper I found in case anyone's interested:
Earlier quoted context omitted.
You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.
I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above... ...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...
Additionally, "The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place."
[1] https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
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.
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…