random number generator with x,y coordinates as seed

Question

I'm looking for a efficient, uniformly distributed PRNG, that generates one random integer for any whole number point in the plain with coordinates x and y as input to the function.

int rand(int x, int y)

It has to deliver the same random number each time you input the same coordinate.

Do you know of algorithms, that can be used for this kind of problem and also in higher dimensions?

I already tried to use normal PRNGs like a LFSR and merged the x,y coordinates together to use it as a seed value. Something like this.

int seed = x << 16 | (y & 0xFFFF)

The obvious problem with this method is that the seed is not iterated over multiple times but is initialized again for every x,y-point. This results in very ugly non random patterns if you visualize the results.

I already know of the method which uses shuffled permutation tables of some size like 256 and you get a random integer out of it like this.

int r = P[x + P[y & 255] & 255];

But I don't want to use this method because of the very limited range, restricted period length and high memory consumption.

Thanks for any helpful suggestions!

Answer 1

I found a very simple, fast and sufficient hash function based on the xxhash algorithm.

// cash stands for chaos hash :D
int cash(int x, int y){   
    int h = seed + x*374761393 + y*668265263; //all constants are prime
    h = (h^(h >> 13))*1274126177;
    return h^(h >> 16);
}

It is now much faster than the lookup table method I described above and it looks equally random. I don't know if the random properties are good compared to xxhash but as long as it looks random to the eye it's a fair solution for my purpose.

This is what it looks like with the pixel coordinates as input:

Answer 2

My approach

In general i think you want some hash-function (mostly all of these are designed to output randomness; avalanche-effect for RNGs, explicitly needed randomness for CryptoPRNGs). Compare with this thread.

The following code uses this approach:

• 1) build something hashable from your input
• 2) hash -> random-bytes (non-cryptographically)
• 3) somehow convert these random-bytes to your integer range (hard to do correctly/uniformly!)

The last step is done by this approach, which seems to be not that fast, but has strong theoretical guarantees (selected answer was used).

The hash-function i used supports seeds, which will be used in step 3!

import xxhash
import math
import numpy as np
import matplotlib.pyplot as plt
import time

def rng(a, b, maxExclN=100):
    # preprocessing
    bytes_needed = int(math.ceil(maxExclN / 256.0))
    smallest_power_larger = 2
    while smallest_power_larger < maxExclN:
        smallest_power_larger *= 2

    counter = 0
    while True:
        random_hash = xxhash.xxh32(str((a, b)).encode('utf-8'), seed=counter).digest()
        random_integer = int.from_bytes(random_hash[:bytes_needed], byteorder='little')
        if random_integer < 0:
            counter += 1
            continue # inefficient but safe; could be improved
        random_integer = random_integer % smallest_power_larger
        if random_integer < maxExclN:
            return random_integer
        else:
            counter += 1

test_a = rng(3, 6)
test_b = rng(3, 9)
test_c = rng(3, 6)
print(test_a, test_b, test_c) # OUTPUT: 90 22 90

random_as = np.random.randint(100, size=1000000)
random_bs = np.random.randint(100, size=1000000)

start = time.time()
rands = [rng(*x) for x in zip(random_as, random_bs)]
end = time.time()

plt.hist(rands, bins=100)
plt.show()
print('needed secs: ', end-start)
# OUTPUT: needed secs:  15.056888341903687 -> 0,015056 per sample
# -> possibly heavy-dependence on range of output

Possible improvements

• Add additional entropy from some source (urandom; could be put into str)
• Make a class and initialize to memorize preprocessing (costly if done for each sampling)
• Handle negative integers; maybe just use abs(x)

Assumptions:

• the ouput-range is [0, N) -> just shift for others!
• the output-range is smaller (bits) than the hash-output (may use xxh64)

Evaluation:

Check randomness/uniformity

Check if deterministic regarding input

Answer 3

You can use various randomness extractors to achieve your goals. There are at least two sources you can look for a solution.

• Dodis et al, "Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes"
• NIST SP800-90 "Recommendation for the Entropy Sources Used for Random Bit Generation"

All in all, you can preferably use:

1. AES-CBC-MAC using a random key (may be fixed and reused)
2. HMAC, preferably with SHA2-512
3. SHA-family hash functions (SHA1, SHA256 etc); using a random final block (eg use a big random salt at the end)

Thus, you can concatenate your coordinates, get their bytes, add a random key (for AES and HMAC) or a salt for SHA and your output has an adequate entropy. According to NIST, the output entropy relies on the input entropy:

Assuming you use SHA1; thus n = 160bits. Let's suppose that m = input_entropy (your coordinates' entropy)

• if m >= 2n then output_entropy=n=160 bits
• if 2n < m <= n then maximum output_entropy=m (but full entropy is not guaranteed).
• if m < n then maximum output_entropy=m (this is your case)

see NIST sp800-90c (page 11)