h a l f b a k e r yi v n i n seeks n e t o
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Please log in.
Before you can vote, you need to register.
Please log in or create an account.
|
True random numbers are actually quite hard to generate in bulk. Generally, 'raw' random bits are created using a hardware device then heavily filtered to get rid of bias and any other non-randomness.
To generate a random number in a range which isn't a power-of-two from random bits, the only valid
method involves repeatedly generating a random number in a power-of-two range, discarding the result if it exceeds the maximum.
For example, to generate an integer in the inclusive range 0..4 (5 possibilities), three random bits would be taken to generate an integer in the range 0..7. If the resultant number was 5,6 or 7 this would be discarded and the method repeated.
Obviously this is wasteful, as several repeats may be made before an in-range number is created.
Where there is more than one value in the 'reject' range, there is an opportunity to salvage some data from discarded results.
The range-limited random number generator simply needs to keep track of the maximum extent of the excess, and apply additional random bits to make up the range.
In the above case, a three-value range is available from rejected numbers: 5..7. Subtracting the minimum and adding an extra bit gives a six-value range (0..5), which is enough for another attempt. Note that this has a single reject value - no further salvage is possible so a full three-bit value must be generated for a third attempt.
By my calculations on average the default method uses about 4.8 bits per number while the salvaging method uses 3.6 bits per number for the example range. I think that's a pretty decent saving, although obviously the saving varies depending on the range required, being best at 2^n+1 and nothing at all for 2^n-1.
HotBits
http://www.fourmilab.ch/hotbits/
Genuine random numbers, generated by radioactive decay [Loris, May 28 2011]
[link]
|
| |
What about mapping the random number to the range? So for example multiplying the random number by 5/8 and then rounding or truncating to get an integer. |
|
| |
I'm guessing there's a problem with my solution. |
|
| |
That method is commonly used, [xaviergist], but it's even more wasteful, since you have to generate extra bits to avoid rounding errors. |
|
| |
(Picky) True random numbers are impossible to generate, because on average, their size is infinite. |
|
| |
//To generate a random number which isn't a power-of-two from random bits// You mean whose range isn't a power of two, right? That one confused me for a bit. |
|
| |
Yep wasteful and it also wouldn't work properly. Some random numbers would have a two-to-one mapping, whereas others would only have a one-to-one mapping. Thus some numbers would get mapped twice as frequently. |
|
| |
Hi Loris, I always thought the general random
number generation process went more in the style
of
1) Generate a table of random bits from a given
seed
2) Take the nth bit-pattern and interpret as a
floating point number between 0 and 1.
3) Scale to required proportions. |
|
| |
But that could be due to it being presented like
that in a couple of languages, rather than being
how they do it in hardware. |
|
| |
e.g. For a random number between 1 and 6 in
BASIC
x = INT(RND(seed)*6)+1
And in Java , the second part is done for you,
depending on the type/size of number you want,
leaving
int throw = generator.nextInt(6) + 1; |
|
| |
But I see you're talking about doing this in
hardware (I think the above is generally
implemented as algorithmic pseudo-random
numbers) but that same scaling method could be
applied, depending on the range of numbers you
want to spit out. |
|
| |
That's what I meant by extra bits, above. A random number between 1 and 6 requires only 3 bits, but the floating point number typically has 32 bits. |
|
| |
Yes, that's pretty much it.
If you have copious random bits, you can use many, and scale the result to the desired range. However this does have an issue in that there will be an excess for some numbers due to the mapping. It may not be much, but it's an issue for all the things you want very good random numbers for. |
|
| |
Pseudo-random number generators are good at generating the many bits necessary for this, but they're not random enough for some purposes. Hardware RNGs can produce very good randomness, but they're relatively slow - of the order of hundreds or thousands of random bytes per second (Hotbits, for example, reportedly generates ~100 bytes per second). |
|
| |
The actual randomness getter is the only part for which hardware is needed. Typically they're written to a file and used as needed (each bit can only be used once). I'm not proposing any additional hardware for the processing, merely an algorithm to eke out a number of random bits to go further. |
|
| |
////To generate a random number which isn't a power-of-two from random bits// You mean whose range isn't a power of two, right? That one confused me for a bit.//
Um, yes. I'll fix that. |
|
| |