Your seed -> woodland coord function is drastically less efficient than it could be

[EthanSteinberg]

A key part of your algorithm is decoding the seed to find an x and z coordinate for a woodland region.

In other words, we have the equation:

seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48

and we need to find x and z (both between -23440 and 23440).

You do this with a very large lookup table of size 2^32. A lookup table of that size is strictly not necessary and we can actually just use a HashMap with 46,881 entries, a reduction of about 5 orders of magnitude. This should also improve your speed quite tremendously, as you can do everything within cache (either CPU or GPU cache).

First, let us make x and z strictly positive by adding an offset of 23440 to each.

seed = (x - 23440) * 341873128712 + (z - 23440) * 132897987541 - 4172144997891902323 mod 2^48

If you simplify this out you get

seed = x * 341873128712 + z * 132897987541 + 7471016896829 mod 2^48

Important point: x and z are now always less than 16 bits

We can now do a bit more simplification, using the fact that 132897987541 is invertible mod 2^48

First, we subtract from both sides

(seed - 7471016896829 ) = x * 341873128712 + z * 132897987541 mod 2^48

Then, we multiply each side by 211541297333629

(seed - 7471016896829 ) * 211541297333629 = x * 341873128712 * 211541297333629 + z mod 2 ^ 48

Finally, we simplify

(seed - 7471016896829 ) * 211541297333629 = x * 1063476645096 + z mod 2 ^ 48

For the sake of simplicity, let seed* = (seed - 7471016896829 ) * 211541297333629 mod 2 ^ 48

seed* = x * 1063476645096 + z mod 2 ^ 48

Now we can make a key insight. z is at most 16 bits, so the upper bits of x * 1063476645096 should be mostly preserved.

Let >> be the bitwise shift operator.

(seed* >> 16) = (x * 1063476645096 >> 16) or (seed* >> 16) = (x * 1063476645096 >> 16) + 1

The key is to think about addition in terms of binary representation. There are two possibilities: the lower 16 bits of x * 1063476645096 and z sum to a number greater than 2^16 (aka there is a carry bit) or they sum to a number less than 2^16 (aka there is no carry bit).

All we have to do is create a lookup table that maps (x * 1063476645096 >> 16) mod 2 ^ 32 to x for all possible x values (which is from 0 to 46880). This table will only have 46881 entries. It turns out that (x * 1063476645096 >> 16) mod 2 ^ 32 => x is a unique mapping, so you can deterministically find the x given (x * 1063476645096 >> 16) mod 2 ^ 32. Note that the overall approach will still work even if it's not a unique mapping, it will just be more inefficient as you will have more values of x to check.

Now you can find x by simply looking at the table entries for (seed* >> 16) mod 2^ 32 and (seed* >> 16) - 1 mod 2^32.

That will get you two possible x values. You can then find two possible z values using the below formula:

z = x * 1063476645096 - seed* mod 2 ^ 48

Check both possible z's and you have your solution.

[leijurv]

well god damn

[0-x-2-2]

Got damn

[EthanSteinberg]

Actually, you can optimize this even further, reducing the runtime by half at the cost of doubling the size of the HashMap.

Instead of a HashMap that only contains entries for (x * 1063476645096 >> 16) mod 2 ^ 32 => x, we can also add entries for (x * 1063476645096 >> 16) + 1 mod 2 ^ 32 => x.

We are lucky that in this case there are still no collisions even with those duplicative entries.

Now there is only one possible x value after doing a lookup in the HashMap, so there is only one possible z value to check.

[SpigotRCE]

bunch of nerds fr