You can take advantage of 64 bit integers by using FFI. It's not too easy to handle, and I'm not sure if you can carry on all of the operations necessary to succeed in this case.
Warning: wall of text ahead.
I've now understood the formula. It's basically a method of numbering spheres arranged as a tetrahedral pyramid
, which when adequately transformed and using 1x1x1 cubes instead of spheres, fills N³, that's why it's bijective for the naturals. The pre-mapping of negative to positive numbers makes it count in the shape of an octahedron centred at the origin.
To be picky, your implementation is actually not bijective, but it's injective, which is good enough, as that guarantees that you get a different number for each coordinate, even if there are numbers that don't correspond to any coordinate. The reason it's not bijective is that your function 'constraint' does not produce zero as an output.
Since zero isn't a possible input to the next phase, it also doesn't produce any of the numbers that the tetrahedral function would return for an input value of 0 in any coordinate, for example for the numbers from 0 to 39 it can only generate four numbers: 14, 24, 27 and 28 (10%), but fortunately the percentage grows as the numbers do. It's basically discarding all numbers that lay in the X, Y and Z planes, i.e. three layers of balls, if you prefer to see it that way. That makes it an injection from Z³ to N, not a bijection.
Here's my implementation of the tetrahedral pyramid method:
Code: Select all
local function tetrahedral(x, y, z)
local ny = x + y
ny = ny * 0.5 * (ny + 1)
local nz = x + y + z
local mod3 = nz % 3
if mod3 == 1 then
nz = (nz + 2) / 6 * nz * (nz + 1)
elseif mod3 == 2 then
nz = (nz + 1) / 6 * nz * (nz + 2)
nz = nz / 6 * (nz + 1) * (nz + 2)
return x + ny + nz
local function z_to_n(z)
return z < 0 and 1 - 2 * z or 2 * z
local function biject(x, y, z)
return tetrahedral(z_to_n(x), z_to_n(y), z_to_n(z or 0))
Note how my z_to_n function can return 0 and therefore in theory biject() is a bijection between the N and Z³.
The tetrahedral function is written in a way that will never suffer 53-bit overflow in the intermediate results if the final theoretical result fits in 53 bits (something that very few binomial calculation algorithms care about, thus reducing their range of proper operation). Division by 2 is always exact for floats, because they work in binary, but division by 3 isn't, so that one needs a case-by-case check in order to only divide by 3 the number that is already a multiple of 3 (actually by 6 which is 3*2, but again, division by 2 is exact).
But tetrahedral numbering is not the only approach to a bijective map, and possibly not the best approach either.
The tetrahedral method is cool, in that you can have one different seed per supported square that lies within an octahedron, and you're fine as long as you don't hit a coordinate that doesn't fit within the octahedron for which there's no overflow (I'll call this the "maximal lossless octahedron" or MLO). But most of the time, in games, you want to work with an NxNxN cube or even NxNxM (if height range is different than area range). And that admits a simpler bijective formula, for which you can easily know the range of values it can take, and can therefore know exactly how far you can push it. Working with the tetrahedron formula, to do the same you'd have to find the biggest cube that can fit within the MLO, and that would mark the limits of your playing area. It's much better to define the limits in advance and play with them until you're satisfied, than to have to stick to limits that are intrinsic to the algorithm being employed, don't you think?
The method is basically to take the coordinates as a mixed radix
representation of the seed. It works as follows (in pseudocode):
RangeX = MaxX - MinX + 1
RangeY = MaxY - MinY + 1
RangeZ = MaxZ - MinZ + 1 -- not used in the seed formula, but used to calculate the range of the seed
Seed = (z - MinZ) * RangeY * RangeX + (y - MinY) * RangeX + (x - MinX)
or, to save a multiplication:
Seed = ((z - MinZ) * RangeY + (y - MinY)) * RangeX + (x - MinX)
Now, the maximum value of Seed is exactly RangeX * RangeY * RangeZ - 1, that is, you have exactly RangeX * RangeY * RangeZ possible seeds when x, y, z are within their respective ranges. When RangeX, RangeY and RangeZ are powers of 2, you can count bits, which even simplifies the calculations more.
For example, love.math.newRandomGenerator
can use two 32-bit input seeds. If you restrict the ranges to, say, 10, 10 and 10 bits, you can have a 30-bit number in the low part of the seed and any arbitrary 32-bit magic number in the high part. That gives you a range of 2^10 = 1024 numbers in each direction, which you can distribute for example like this: from -512 to +511 inclusive, plus a magic number from 0 to 4294967295. Or you can have a cuboid instead of a cube, using 11 bits for X and Y and 10 bits for Z. Or 16 bit for x, 16 bits for y, 16 bits for z and 16 for the magic number; the latter two would go into the high part. That would give you a range of -32768 to 32767 (or from 0 to 65535 or however you want to distribute it) in every direction, and a range of 0 to 65535 for the magic number.
If you've read all the way up to here, congratulations!