SOLVED: Which binary operator or function results in the least collisions?

Question

Suppose we have two longs, x and y. What operator or function involving x and y would produce another long, z, which is least likely to be equal to the result of applying the same operator or function to different of x's and y's?

Ex: Addition would be a poor choice. 1+4=5, but 2+3 also equals 5.

EDIT: Let me explain why I'm asking this question. I'm creating a space rpg game. The game's environment (solarsystems) will be procedurally generated from two seeds. These seeds consist of the x and y coordinates of the system in the universe. So there is a good probability that the player might encounter the systems at (500,501) and (501,500) over the course of his adventures. I need a way to these the solar systems generated unique. But also, I want to make sure that as many coordinate pairs as possible will produce unique seeds.

EDIT 2: I tested two of the solutions given to me. Accipitridae's answer was far superior to Artelius's answer. Here's the code to test the solutions:

HashSet<Long> set = new HashSet<Long>();

 for(int x=0; x<1000; x++)
  for(int y=0; y<1000; y++)
   //I commented out one of the solutions at a time
   set.add((long)(((x&0x7FFFFFFF) << 33) | ((y&0x7FFFFFFF) << 2) |   ((x>>>62) & 2) | (y>>>63)));//Artelius
   set.add((long)(x - y * 7046029254386353131l));//Accipitridae

 System.out.println(set.size());

From the size of the HashSet, I could tell how many unique seeds were generated through each method. For these parameters, Artelius's solution generated 2048 unique longs, while Accipitridae's generated 1000000, meaning that there were no collisions at all.

Thank you all for you effort in trying to solve this problem. :)

Answer 1

As long as you limit the set of possible output values to the SAME set of values as the operands you are using as operands, then you cannot do any better than addition. Addition, actually, is probably the best possible choice, because it is simplest. (See analysis below)

There are 2^64 possible longs, so there are 2 ^ 127 possible unordered pairs of longs, and only 2^64 possible longs for an answer, so the best possible distribution ratio is to have 2^ 63 different pairs that give the same answer, which addition, (with rollover) in fact, will do

EDIT: based on comments below.

however many (say it's N bits) a long is, there are 2^N different longs, so there are 2^N x 2^N ordered pairs of longs, but for the purposes of this analysis, using two longs x, and y is exactly the same as using y and x (the binary op is assumed to be communitative), so there are 2^ (2N-1) unordered pairs of longs.

so using unordered pairs (half as many) there are 2^N x (2^N-1) or 2^ (2N-1) pairs of longs without duplicates. (If N = 64, that's 2^127) So the maximum "distribution" of assignment of answers (from the smaller set of 2^64 longs) to the unordered pairs of operands (the larger set of 2^ 127 pairs) is if they are equally distributed. Thats what addition would do, because for each of possible long in the set of all longs, the sum of it with every other long (with rollover) will be a set of ... every long.

the only thing using ordered pairs does is allow you to use a non-communtative operand as well, but then you have to deal with all the cases where the answer is not in the set you are using for operands (like 5/4 )but even if you just assume rounding, the only impact on the analysis is that by using ordered pairs you get 2^2N different pairs of operands, instead of 2^(2N-1).

What you might do is limit the set of integers to be used as the operands to less than the square root of the number of possible longs (so if you are using 64 bit longs, limit your input values to 32 bit longs) Then, if you want absolutely no overlap or duplication (No case where A op B = same value as any other C op D), you can use the multiplication operator but for each value X in the smaller set of potential operands, choose the Xth prime number as the multiplicative operand. that way, no matter what two values A and B you randomly pick (from 1 to Max) the operantion would be multiplication of two different primes. This means the set of possible operands has to be smaller than the set of prime numbers equal to or less than the maximum possible value you are using for operand (if it's 64 bit unsigned longs, that 2^64)

2nd EDIT: based on yr specific problem, the set of possible operands is limited to the dimensions of a computer screen, considerably less than the number of longs, (no matter what platform you are on) So a very easy and obvious way to guarantee that every pair of possible screen cooridinates will generate a distinct and different seed key is to simply left shift the value of one coordinate sufficiently to guarantee no bitwise overlap with the other coordinate, and then bitwise Or the result with the other coordinate.

So if your screen is say, 3000x3000, then long lngVal = (x<<12 | y) would do it with minimal computational overhead as well.

Answer 2

If (x1, y1) and (x2, y2) are two random pairs of inputs, then let f1 = f(x1,y1) and f2 = f(x2,y2).

What you want to do is minimise

P( f(x1,y1) = f(x2,y2) )
 = P(f1 = f2)
 = sum for i in [LONG_MIN ... LONG_MAX]
        of P(f1 = i) * P(f2 = i)
 = sum for i in [LONG_MIN ... LONG_MAX]
        of P(f1 = i)^2

So you want to minimise the sum of the squares of the probabilities of each of your function's outputs. Since the sum of the probabilities must be 1, we know:

sum for i in [LONG_MIN ... LONG_MAX]
     of P(f1 = i)
  = 1

And we also know that for all i, P(f1 = i) is between 0 and 1 (inclusive). Intuitively, then, minimising P(f1 = f2) is a matter of making the probability distribution of f1 as even as possible. (This can be proven mathematically but it's not really important to the question.) Ideally, P(f1 = i) and P(f1 = j) should be the same for all longs i and j.

Now let's look at some different possibilities for the nature of x and y.

First the general case, where x and y are uniformly distributed over the range of a long. (In other words, x is equally likely to be anything a long can be. So is y.) In this case, we can let f(x, y) = x+y, or f(x,y) = x-y, or f(x,y) = x XOR y, or even f(x,y) = x and (assuming normal integer overflow) we find that we have a uniformly distributed f, too, which means these functions are all "optimal".

But the f(x,y) = x example shows you that there's really not that much you can gain here.

However, in practice, your x and y will probably not be uniformly distributed. For instance, if x and y both drawn randomly from the range [0, 9999], then using f(x,y) = x + y * 10000 will always produce different output for different input.

If, in each (x, y) pair, x and y are very likely to be near each other, for instance (1240,1249), (1,3), (-159720,-159721), then f(x,y) = x is actually quite a good candidate function.

If x and y are "probably not huge", then you should combine the 16 low bits of x with the 16 low bits of y, i.e. f(x,y) = ((x&0xFFFF) << 16) | (y&0xFFFF), because the lower bits will be more evenly distributed than the upper bits.

This works very well if x and y are never negative. But if they are, the sign bit (that tells whether the number is positive or negative) might be more evenly distributed than some of the 16 low bits. So you may want to use it instead. E.g.

f(x,y) = ((x&0x7FFF) << 17) | ((y&0x7FFF) << 2) | ((x>>30) & 2) | (y>>31)

As the "probably not huge" case is quite common, I think this function would actually work quite well in general.

Answer 3

I like the answer and anlysis by Artelius. Especially the proposal to use

f(x,y) = x + y*K

for some constant K is interesting and I'd like to just add a few more thoughts. What I'm doing here is not new, but very closely related to the Fibonacci hashing, which I think has been proposed by Knuth.

If we are using 64-bit integers then a collision f(x1, y1) = f(x2, y2) means

0 = (dx + dy * K) mod 2⁶⁴,

where dx = x1 - x2 and dy = y1 - y2. This is the same as

K = -dx*dy^-1 mod 2⁶⁴,

where dy^-1 is the modular inverse modulo 2⁶⁴. If we want to choose the K such that f(x1, y1) != f(x2, y2) whenever the differences dx and dy are both small then we have to choose K such that

K = -dx*dy^-1 mod 2⁶⁴,

has no solution such that both dx and dy are small. This can be achieved for example by choosing K close to phi * 2⁶⁴, where phi = (sqrt(5)-1)/2 is the golden ratio. The golden ratio has a very special continued fraction expansion, i.e. in a certain sense it is a number that is hard to approximate well with a fraction.

Hence, for 64-bit unsigned integers the following functions could be used

f(x,y) = x + y * 11400714819323198485;

or equivalently when using signed 64-bit integers

f(x,y) = x - y * 7046029254386353131;