Quick random shuffle function in plain C

Question

For years I've thought about this, but never managed to implement one. I'm talking about a quick, efficient C function that accepts an integer numeric value (e.g. 16 bit) in input and gives a completely different number of the same bit-size in output, but "takes into account" all the numbers that were already given, although not by using real memory, but by math magic. Sorry, English is not my native language, what I mean is that the function should map one-to-one randomly but without any duplicates.

Possible applications I imagined were for example one of those pixel-crossfade graphics routines where you replace the old pic on the screen with the new one, pixel by pixel. The coordinates should be chosen randomly, and once a pixel is replaced, it should not be addressed again (no duplicates). All of this naturally by a small, quick and efficient function math-based (it would be easy to implement this using memory, but it's not what I want).

Clearly a "bit-reverse" solution won't work because it won't look random. Even swapping e.g. bit 3 with bit 11, etc.. to create more "chaos", invert some bits, etc.. didn't really look good, so I'm looking for a pure mathematical, really random-looking, function, capable possibly of at least 16bit, and using as little memory as possible (no precomputed tables, as the first application I'd finally use it is on a micro-controller system to make an old-style game with public domain hardware and software).

Can you help please?

Answer 1

What you're looking for is basically a cyclic generator of the group corresponding to the number of pixels you want to crossfade. In the most general case, this is any coprime to the size of your group. By way of doing all calculations modulo your number of pixels, you get the appearance of randomness without this being actually random.

Let's say you have a domain of size 32 and start with a seed of 5. By constantly adding the coprime of 15, you would get the sequence of

(5, 20, 3, 18, 1, 16, 31, 14, 29, 12, 27, 10, 25, 8, 23, 4,...)

This probably will seem random enough for your requirements.