jeudi 5 février 2015

Generate random floats from random bytes without bit-twiddling

Assuming I have a good-enough(tm) stream of random byte values, is there a mathematical way to convert these into (0 < n < 1) floating-point values that does not need to know the internal format of the floats?


I'm looking for something that:



  • Doesn't require bitwise operations (on the floats), and

  • Is an iterative process that we can know will give a good value after n iterations, where n is a function of the output precision.

  • A general process that can be used for floats of any precision, by simply changing the number of iterations, ie consuming more input bytes to generate a double than a single-precision float.


The naive solution is to just build yourself a big integer from a few bytes, and then simply convert to float divide by 2^n, but I can't see how to do it without messing up the distribution.


Another idea is something like this (pseudocode):



state := 0.0
n := requiredIterations(outputPrecision)
for(1..n)
nextByte := getRandomByte()
state := state + nextByte
state := state / 256
end
return state


It seems like this should work, but I don't know how to prove it :)





Aucun commentaire:

Enregistrer un commentaire