Site Stability Read more... ×

# good random permutation?

This topic is 1905 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 :)

##### Share on other sites
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. Edited by Álvaro

##### Share on other sites
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;
`

##### Share on other sites

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!

##### Share on other sites
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?

##### Share on other sites

World generation:

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

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

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11