2
$\begingroup$

There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to this:

Given an n-tuple of integers, how do I derive a stateless pseudorandom number / hash value in the half-open interval [0,1)?

The usual “solution” people use in this situation is to multiply the parameters by some large primes, or bit-shift them, or do any other complex calculation which produces a result that is “random enough” for the given purpose. I guess these algorithms have been cargo-culted over a long time, maybe from a PRNG implementation.

Instead of copying one of the circulating code snippets, I'd like to really understand what's going on here. Is there an algorithm or a set of algorithms which should typically be used in this kind of situation, and if so, what's the proper way to choose the constants?

$\endgroup$
  • 8
    $\begingroup$ What properties do you want the hash function to have? What do you mean by stateless? How many output bits do you need? Have you looked at universal hash families? Have you looked at cryptographic hash functions? $\endgroup$ – jbapple Apr 29 '15 at 7:29
  • $\begingroup$ The function should return values which are “random enough for any practical purpose”. If they are to be visualized as gray scales in a grid (which is a somewhat plausible model for what it comes down to in many cases), there shouldn't be a pattern recognizable to the eye. (I know this isn't terribly precise but I don't know how to put this better, sorry. Humans are amazing pattern recognition machines…) $\endgroup$ – user3426575 Apr 29 '15 at 18:54
  • $\begingroup$ By stateless, I mean that there shouldn't be a state carried from one invocation of the function to the next one; if invoked later with the same parameter tuple, the function should return the same result. $\endgroup$ – user3426575 Apr 29 '15 at 18:55
  • $\begingroup$ I don't generally need many output bits (as compared to a cryptographic hash function). The exact number varies from situation to situation; in one case, I need a uniformly distributed value from 1 to 20, while in other cases, I need a floating-point parameter which usually requires about 8–16 bits to be “smooth enough”. $\endgroup$ – user3426575 Apr 29 '15 at 19:08
4
$\begingroup$

Every hash function is stateless; that's part of the definition of what it means to be a hash function.

A simple approach is to take a representation of the input in binary, using any standard encoding for the integers and for $n$-vectors of integers, and then hash the result using your favorite hash function. The output will be a binary string. Treat it as the binary representation of a number in the range $[0,1)$ (put a decimal point before the start of it, and interpret it in base 2). That's your output.

Then, choose a suitable hash function for hashing binary strings. If you need it for cryptographic purposes, you could use SHA256. If you need it for non-cryptographic purposes, there are many standard, fast hash functions; choose one that meets your requirements. Since you didn't state any precise requirements in the question, we have no basis to select among any of the standard solutions.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy