State of the art of random double generation

Re:State of the art of random double generation by TheLoneWolfling on Friday April 10, 2015 @05:41PM (#9357250)

You can do better than 8, as mark-r said.

Do as I mentioned, but batch requests.

For example, if you generate 89 numbers from 0-128 inclusive at once, you'll need, on average, 624.3 bits of entropy to generate them, whereas the optimal is 624.0 bits. That's an average of 7.0 bits of entropy per number generated. (It works out to something like 1.00054 x optimal.)

So, generate a number from 0 to 128^k-1, and split it base 129, for some value of k, returning the k random numbers generated this way. For sufficiently large k you will be able to use arbitrarily close to the optimal number of bits of entropy per request.

Unfortunately, this requires you know in advance what the range of the random numbers to generate will be.

[ Parent | on HN ]

Re:State of the art of random double generation by SamReidHughes on Saturday April 11, 2015 @05:29AM (#9358957)

You don't need to know in advance. Generate a big r from 0 <= r < s. When calling randint(n), return r mod n and update (r, s) = (r/n, s/n), unless r >= s - (s mod n) in which case reset s and regenerate r.

[ Parent | on HN ]