I have a series of integers which I want to convert to random integer (64 bit). The idea here is to produce random numbers very quickly. The issues that good quality random numbers are required with a low collision rate to ensure low correlation between entities. A series of integers are input and a number of desired samples are required that are a random as possible.
The hash?
The random hash is taken from Numerical recipes book and is fast as it used just bit shifts and XORs. This should be very fast. The inputs are a 64 bit integer and output is a 64 bit integer. Some of the numbers can work on 32 bit, so this might be an advantage later on in ensuring there is no overflow.
How to combine hashes?
I understand about using XORs in terms of maximizing entropy and ensuring the combination doesn't exceed 64 bits. However the issue is that if I have series of nested loops over integers then with 2 loops I may get the following
A = 0, B = 1
and then I have A= 1, B = 0
and these will be equivalent so I get a collision i.e.
(Hash(A=0) XOR hash(B=1)) = (Hash(A=1) XOR hash(B=0))
One way around this might be to do the following:
Hash(A) + k*Hash(B)
where k = [int]
, say = 5
What worries me here is that if I have to use a 64 bit representation for i and j, then I am likely at some-point to reach over flow as I might get j near the MaxInt and multiplying by k is going to result in exceeding MaxInt. However if I assume that j is 32 bit, if k is low then I am careful about removing a deductable from i, the MaxInt issue can be avoided. Also I shall have to watch that the sum of i and j doesn't exceed the Max int. I can see using pure XOR's would be useful but it is troubling because of the collision rate.
Using another algorithm here with an increased key length (block cipher) maybe the way forward as we can increase the key length with something like Blowfish to handle many 64 bit integers concatenated to form a key. What worries me with Blowfish is slow with regard to handling the key and this needs to be super quick.
Are there any recommendations out there for a better way to handle this problem?
In summary,
Have inputs:
A: 64 bits
B: 32 bits
C: 32 bits
D: 32 bits
E: 32 bits
The output should be an integer/double that is has the fewest repeats/collisions as described above. The output is not being used for anything other than generation of random numbers, but important that those random numbers are not correlated for the input.
The hash currently being tested is:
inline Ullong int64(Ullong u)
{
Ullong v = u * 3935559000370003845LL + 2691343689449507681LL;
v ^= v >> 21; v ^= v << 37; v ^= v >> 4;
v *= 4768777513237032717LL;
v ^= v << 20; v ^= v >> 41; v ^= v << 5;
return v;
}
inline Uint int32(Ullong u)
{
return (Uint)(int64(u) & 0xffffffff);
}
Returns hash of u as a double-precision floating value between 0. and 1.
{
return 5.42101086242752217E-20 * int64(u);
}