3 ms·

Related: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator A pseudo-RNG that cycles throu

Related: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator A pseudo-RNG that cycles through a all elements of a modulo-ring. Example for a 2^32 bit cycle: X(n+1) = (a * X(n) + c) mod m a = 134775813 c = 1 m = 2^32

leni536 9y ago
My approach would be something like this, but with a very "poor" generator with the parameters a=81007, c=0 and m=2^17. This approximates a low discrepancy sequence (additive recurrence with alpha=1/golden ratio). Then I would calculate x and y values using the hilbert curve and the calculated pseudorandom number as the index (more precisely two Hilbert curves next to each other, so it covers a 512x256 rectangle). On today's CPUs it can be calculated quite fast (shameless selfplug: https://github.com/leni536/fast_hilbert_curve https://github.com/leni536/fast_hilbert_curve). I suspect that the resulting pattern on the screen would be less random looking, but more uniform without any obvious pattern.
- schindlabua 9y ago
  Cool! I was just looking up hilbert implementations yesterday, so that's super useful. Thanks! (quick note: in your source the function is called hilebert instead of hilbert)
  - leni536 9y ago
    Fixed, I also added a Wolfram Mathematica module that can be used with LibraryFunctionLoad.
barrkel 9y ago
Indeed; and careful selection of parameters for the LCG can truncate the ring to most arbitrary powers of two. And if you're willing to live with slight inefficiency (no more than twice as much work), an arbitrary modulo ring (shuffled sequence) can be produced by creating slightly larger range and skipping values that are outside the range. This is a question I asked on SO some years ago relating to this problem - producing a shuffled range of numbers without allocating an array: https://stackoverflow.com/questions/464476/generating-shuffled-range-using-a-prng-rather-than-shuffling https://stackoverflow.com/questions/464476/generating-shuffl...
xigency 9y ago
I thought of this too, but it might be a bit more taxing on an old CPU to do excess multiplication than a simple XOR and test.

leni536 9y ago

My approach would be something like this, but with a very "poor" generator with the parameters a=81007, c=0 and m=2^17. This approximates a low discrepancy sequence (additive recurrence with alpha=1/golden ratio). Then I would calculate x and y values using the hilbert curve and the calculated pseudorandom number as the index (more precisely two Hilbert curves next to each other, so it covers a 512x256 rectangle). On today's CPUs it can be calculated quite fast (shameless selfplug: https://github.com/leni536/fast_hilbert_curve https://github.com/leni536/fast_hilbert_curve). I suspect that the resulting pattern on the screen would be less random looking, but more uniform without any obvious pattern.

schindlabua 9y ago
Cool! I was just looking up hilbert implementations yesterday, so that's super useful. Thanks! (quick note: in your source the function is called hilebert instead of hilbert)
- leni536 9y ago
  Fixed, I also added a Wolfram Mathematica module that can be used with LibraryFunctionLoad.

barrkel 9y ago

Indeed; and careful selection of parameters for the LCG can truncate the ring to most arbitrary powers of two. And if you're willing to live with slight inefficiency (no more than twice as much work), an arbitrary modulo ring (shuffled sequence) can be produced by creating slightly larger range and skipping values that are outside the range. This is a question I asked on SO some years ago relating to this problem - producing a shuffled range of numbers without allocating an array: https://stackoverflow.com/questions/464476/generating-shuffled-range-using-a-prng-rather-than-shuffling https://stackoverflow.com/questions/464476/generating-shuffl...

xigency 9y ago

I thought of this too, but it might be a bit more taxing on an old CPU to do excess multiplication than a simple XOR and test.