@demofox I used to work on a marketing platform that had this competition code dispenser system that would dispense predetermined codes in a random order - it did this by pre-populating a table with millions of rows and then randomly selecting indexes and marking them used... I came up with a stateless shuffling system to remove the setup / indexing overheads. I'd excitedly tell people about it to be met with much eye-glazing ;)
It's nice to see that it's actually a thing in the real world.
@toerror that is so cool. If you haven't seen the term "format preserving encryption" is the formal term for it. It's a weird name, but it's used a lot. Credit card companies use it to generate the next credit card number, I've heard :)
@demofox It's funny how you can search for a description of a thing and never find it - you have to know the magic words! ;)
I was actually very concerned about the randomness of my shuffle at the time ( I was using a system that echoed a real deck shuffle - taking modulo groups of cards and moving them around where the block size and distance moved was determined by a fixed seed ) - couldn't even find a way to measure how random a shuffled set was outside of eyeballing it..
@demofox anything involving modular arithmetic makes me happy. I don't think I fully understand the choice of a large irrational prime (as opposed to, say, a large prime number with a good distribution of set and unset binary digits) but this sort of thing is perfect for shuffling.
@demofox one thing I like doing is using multiplication by a large prime as a fast invertible randomisation operation. Like, if I want to use a pointer as a key in a tree and the data structure works better with random keys, I can treat the pointer as an integer, multiply it by a large prime and use that as a key. The modular inverse of the prime can then be used to go back from a key to a pointer if needed.
@nickappleton yeah, so this does that exact thing, and that stuff is great. It makes a nice bijection / shuffle. The irrational makes it have the low discrepancy properties.
If you want to know more about that, here's a video. apologies that it's 50 minutes though :P
The first half is the relevant bits. https://www.youtube.com/watch?v=tethAU66xaA
@demofox thanks for posting! I watched the first half of the video (need to sleep now) and have a much better idea of what this is being used for now. Well presented!
@demofox Great article! At first I thought, extended Euclidean algorithm is not constant time, but as far as I can tell its output can be cached as a one-time setup instead of computed live during inversion.
@demofox oh nice. i wrote one that pulls items from a set (a shuffling ring buffer, see screenshout for demo output), but doing this without a set at all is excellent :)
@lritter I can always count on you to understand and appreciate these things, and have done similar work. It's nice not to just be a crackpot in the corner 😀
@demofox a neat application of this is possibly for LDS discrete sequence importance sampling; simply N is not the element count, but sum of the element values and then one can do a binary search over the discrete CDF. This could be useful for importance sampling when elements are sorted according to some other diversity metric, like spatial distance or whatever.
@BartWronski that's a neat idea!
I've also tried a bit to get this working in 2d. I thought I had a nice solution but then I tried at different resolutions, and it fell apart.
@demofox would Hilbert curve remapping work? I have this snippet from some old article (can't find it now) for converting 1 LDS random number to 2, works not ideal, but pretty ok. Then you can start with just 1D. :)
Add comment