Re: Better use of random number genator bits?
- From: "The Last Danish Pastry" <clivet@xxxxxxxxx>
- Date: Mon, 6 Mar 2006 10:17:56 -0000
"DAC" <Mister@xxxxxxxxxx> wrote in message
news:440be48e$0$1279$afc38c87@xxxxxxxxxxxxxxxxxxxxxxx
If I have a random number generator creating random binary digits (0
or 1), and I want to construct a random integer between 0 and say
40, it appears the accepted no biased way is to take 6 binary digits
which will represent numbers 0 to 2^6-1 (63).
So to obtain a number between 0 and 40 I must ignore any randomly
generated numbers above 40. This means that on average 24/64 = 37.5%
of the time I will have to get another number (6 more bits), and
37.5% of those times another 6, such that on average we will have to
obtain 10.5 bits to make a number between 0 and 40 because the
random bits are base 2 and not base 40.
So what I am asking is, if the number is greater than 40 what can I
do with the bits I have already so that instead of getting another 6
bits I can get less than this, or reuse these bits, with out
introducing any bias what-so-ever, if this is possible at all.
One Idea I have, but havent done any work on yet, is if both of the
first two numbers are over 40, you can add them together and
subtract 80 to get a unbiased random number between 0 and 47 and so
I can again check if this number is less than 40, effectively saving
need for 6 more bits.
This is important for us because for example to shuffle a deck of
cards we are taking 51 random numbers (between 0 and 51 down to
between 0 and 1). This on average is a total of about 2880 bits to
shuffle a deck (of course there is no maximum on this number and I
have encounter one situation that took over 13,000 bits), where you
should really only need log2(52!) = 226 bits to specify a specific
shuffle. So at the moment we are using on average 10 times as many
bits as we really need - and quantum generator modules are expensive
and soon we will need the numbers at a rate faster than we can
produce them.
Also another way we know is to produce a 226 bit random number but
the math to do the 226 bit division/modulus etc to produce the
actual card sequence is to slow on current computers to be fast
enough for our implementation, and obviously we cannot have a look
up table of size 52!. We are working on embedded FPGA hardware to do
256 bit math but would be great if any of you math experts here
could help us use less bits in generating a random number working
with standard integer sizes (32bit).
If you need a random integer in the range 0..n-1, look for some power
of n which is just less than a power of 2.
For example, suppose n=40, then 2^16=65536 is a good choice, because
40^3=64000.
Proceed as follows:
1) Generate a 16 bit random integer. Let us call it R.
2) If R is greater than 63999 [which will happen about 2% of the
time], discard it and go back to step 1.
3) A = R mod 40
B = (R div 40) mod 40
C = R div 1600
A, B and C are three random integers in the range 0..39.
--
Clive Tooth
www.clivetooth.dk
.
- Follow-Ups:
- References:
- Prev by Date: Re: On The Improbability of Root Divisibility
- Next by Date: Re: " Solving f( 2*x, y/(1 -x*y) ) = 2 *f(x ,y ) + x + 1/y , a model ? "
- Previous by thread: Better use of random number genator bits?
- Next by thread: Re: Better use of random number genator bits?
- Index(es):
Relevant Pages
|
