good random permutation?

Lode · 2014-08-03T22:54:07

Hello, I'm looking for a way to map a 31-bit positive integer (leaving some room for Java!) to another 31-bit positive integer, for purpose of random world generation, with the following properties: -if you go through the inputs in sequence, the resulting output sequence should be a good pseudo-random sequence -it should not require state. So a linear congruence generator or similar will not work afaik. Instead, it should be able to give you the output for any of the inputs at any time, no requirement to go through it in order. -it should be fast, so cryptographic hashes are probably not it -it should be stable: always give the same output for the same input (so no true random generator ) -each result is unique, that is, every possible integer is output by one input integer (not the most important requirement, but would be nice, each output value should have equal probability). So some arbitrary bit twiddling and multiplications won't do it either I tried to implement something similar to the following one: http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/ but it's actually not that great, I want to use a seed value as well, and while this one works great for some seeds, it does not for many as well and to make it even more annoying, it gives too similar patterns for seeds that are near each other (so if you generate for coordinates x and y a random world temperature with seed 1000 and a random height with seed 1001, they will be too correlated. Or something like that, in any case the patterns are ugly with nearby seeds). Does anyone have suggestions for such a function? Thanks a lot!

Math and Physics Programming

Started by Lode July 13, 2014 08:14 PM

14 comments, last by Lode 9 years, 8 months ago

Lode

1,003

Author

August 03, 2014 01:03 PM

Thanks a lot!

In the end I went with a hybrid with Álvaro's suggestion and irreversible's example :)

With seed a fixed constant that determines the world, and x the input number, my first implementation was:

x ^= (seed ^ 1234567890);
x = (x + 1234567890) & 2147483647;
x = (x * 1000000001) & 2147483647;
x = (x >> 18) | (x << 14);
x = (x * 1000000005) & 2147483647;
return x;

But that had noticable patterns still so not good. But then I combined it with irreversible (the order in which things happen is based on it, the numbers not), giving this:

x ^= (seed ^ 1234567890);
x = (x * 1000000001) & 2147483647;
x = (x ^ ((x << 6) ^ (x >> 26))) & 2147483647;
x = (x * 1000000001) & 2147483647;
x = (x + ((x << 5) ^ (x >> 12))) & 2147483647;
return x;

And that seems to work quite well indeed :)

Homepage | LodePNG

alvaro

21,604

August 03, 2014 02:07 PM

You have to be a little bit more careful. The operation g(x) = (x ^ ((x << 6) ^ (x >> 26))) & 2147483647 is not injective:

g(0) = g(1431655765) = 0

So your function ends up not being a permutation. With seed = 0:

f(0) = f(297859934) = f(719478613) = f(1927211019) = 1905156899

EDIT: I didn't check carefully, but `x = (x + ((x << 5) ^ (x >> 12))) & 2147483647;' is probably also problematic.

alvaro

21,604

August 03, 2014 02:17 PM

Would this be too slow for your program?

  x = (x ^ seed ^ 1234567890) & 2147483647;
  x = ((x << 5) ^ (x >> 26)) & 2147483647;
  x = (x + 675788137) & 2147483647;
  x ^= 751504984u;
  x = (x * 2020831389) & 2147483647;
  x = ((x << 15) ^ (x >> 16)) & 2147483647;
  x = (x + 1804049603) & 2147483647;
  x ^= 1028562816u;
  x = (x * 1430376653) & 2147483647;
  x = ((x << 15) ^ (x >> 16)) & 2147483647;
  x = (x + 1804049603) & 2147483647;
  x ^= 1028562816u;
  x = (x * 1430376653) & 2147483647;
  return x;

Lode

1,003

Author

August 03, 2014 08:50 PM

Thanks for pointing that out. That last one works nicely. But if I remove the last 4 lines (before return x), then the patterns look ugly. Seems like that additional repetition of similar things fixes it. So, works great, but I'm going to experiment to try removing some lines :)

Do you have any explanation why some of these give ugly patterns in results, while others look very random? Thanks!

Homepage | LodePNG

alvaro

21,604

August 03, 2014 10:29 PM

I duplicated the last four lines precisely because I also saw some ugly patterns. What are you doing with the output exactly, where you see the patterns?

Lode

1,003

Author

August 03, 2014 10:54 PM

World generation:

On the left: ugly patterns of trees (the dots)

On the right: good pattern of trees with your code :)

Homepage | LodePNG

good random permutation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

good random permutation?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines