Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is the proper/canonical way to do this?

For example, $0 < r1 < 1$ and $0 < r2 < 1$. Presuming uniformly distributed probabilities for the two, combining/averaging them is going to bias very quickly towards $0.5$.

The specific use case I have is a game/simulation I'm programming. An entity has a random number it was given that's specific to it; Their individual behaviours also have random numbers associated with them. For the purposes of most behavioural calculations, I only use the behaviour random number, but for a few I want to incorporate the entity's random number. Simply averaging them will result in less randomness.

Desired Outcome : Deterministically combine more than one source of entropy

So “Entity A” may have a small random number, and so most of its attributes are skewed small. It's behaviour random number happens to be big, so most of its behaviour attributes are skewed large. When combined the two random numbers deterministically result in $n$, and so some of its behaviour attributes skew towards $n$.

RE: Off-Topic

My question is not specific to game development. The particular use case is. How do cryptographers deterministically combine sources of entropy? I assume they have uses case for this outcome.

share|improve this question
2  
can't you just hash them and map the hash to 0..1? –  CodesInChaos Jan 4 at 23:18
    
@CodesInChaos huh, yes I could. Is that the proper way to combine two sources of entropy? [fwiw, it's javascript, so I have Math.random for free, but would need to implement sha1/another hash in code.] –  Shad Jan 4 at 23:27
    
I think the canonical way to combine two numbers uniformly distributed between 0 and n is to just add them mod n. (Eg, XOR is often used for doing so, and it is just bitwise addition mod 2.) In the case of floating point, however, it may introduce precision bias due to precision limitations. –  B-Con Jan 5 at 0:18
1  
cleaned up some comments –  mikeazo Jan 8 at 14:04
1  
Note of dangers of combining many sources of entropy for cryptography: blog.cr.yp.to/20140205-entropy.html –  catpnosis Feb 10 at 16:35
show 1 more comment

3 Answers 3

up vote 5 down vote accepted

Set $r = r_1 + r_2 - \mathsf{floor}(r_1 + r_2)$. One (possible) advantage of this approach is that the result will be uniformly random in [0, 1] even if only one of $r_1$, $r_2$ is uniformly random. (Assuming the two values are independent.)

In Python you can also express this as

r = (r1 + r2) % 1.0
share|improve this answer
    
Thanks! so simple! –  Shad Jan 5 at 14:30
    
In some languages there is a frac(x) which equals x - floor(x) for non-negative values of x (I'm not sure how it behaves for negative values) –  leemes Jan 6 at 18:58
add comment

Combining two independent random variables that are uniformly distributed between $0$ and $2^n-1$ is rather easy: Both are $n$-bit numbers and every bit is set to $1$ with probability $\frac12$. Therefore, the same is true for their exclusive OR, which will also be uniformly distributed between $0$ and $2^n-1$.

Now, JavaScript's Math.random() pseudo-randomly returns a number in $(0,1)$. Converting that number into an integer $n$-bit integer is easy enough:

var r1 = Math.floor(Math.random() * Math.pow(2,n));

$n$ cannot be greater than 32 in my browser (other implementations may vary) or the resulting integer will always be even.

Now, to combine two of those integers, you can use exclusive OR:

var r = r1 ^ r2;

JavaScript operates on signed 32-bit integers, so $n$ has to be less than 31 to avoid wrapping and signs.

To convert the obtained integer into a value in $(0,1)$, just do this:

r = (r + 1/2) / Math.pow(2,n);
share|improve this answer
    
Awesome, thanks! any reference you can provide regarding the 0 -- 2^n - 1 would be appreciated! –  Shad Jan 5 at 14:33
    
I'm not sure I know what you mean. Are you talking about deriving an integer from a pseudo-randomly generated floating point number or about the uniform distribution of the exclusive OR? –  Dennis Jan 5 at 18:00
    
hah, sry, when I first saw that expression, I was thinking it was something like a trigonometric identity (e.g. 1 - sin^2 x); But I see now it's just a reference to binary order-of-magnitude. –  Shad Jan 5 at 20:56
add comment

If you just want to combine them, you can just add them. You will get an even distribution between 0 < r < 2. An alternative is to get the bytes of the floating point numbers, and XOR them. The result may not be a valid floating point number however. You may also convert the floating point numbers to a string, with arbitrary precision that suits you, and hash them together. Either hash(r1) + hash(r2), or hash(r1+r2), or hash(hash(r1)+hash(r2)), where + is Javascript concatenation for strings. There are public hash libraries for SHA, BCrypt, etc.

share|improve this answer
8  
The sum of r1 and r2 will have an Irwin–Hall distribution, which is not at all uniform. –  Dennis Jan 5 at 4:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.