A particular random number generator returns positive integer n with probability 1/(2^n). (ie '1' with probability 1/2, '2' with probability 1/4, '3' with probability 1/8, etc.)
Using this random number generator, write an algorithm which chooses a random integer from 1 to 37 with equal probability.
The main portion of the algorithm below will work for a range of integers that's a power of 2. So that portion will be called asking for a number in the range 1-64 repeatedly until a number between 1 and 37 is found. (should average less than 2 calls to the 1-64 part):
As you are given a range that is a power of 2, if the RNG produces a 1, narrow the range to the first half of the range and recurse (call itself) with this narrowed range. If the RNG produces a 2, narrow the range to the third quarter of the range in the call, and recurse. If the RNG produces a 3, narrow the range to the seventh eighth of the original range and recurse, etc. Going like this, a certain value will reduce the range to 1 choice, such as, when called with a range 1-64, a value of 6 would narrow the range to the 63rd 64th, that is the value of 63. So if the RNG produces a number higher than this (7 on up) choose the last value in the range (in this case 64).
As you recurse, with narrower ranges, the value for which you decide that above it you choose the last number will change, so for example if the range has been narrowed to 17-20, getting a 1 will narrow the range to 17-18, getting a 2 will effectively choose 19, and above 2 will give 20.
So the outer part of the algorithm is given by:
DO
r = randomNo(1, 64)
LOOP UNTIL r <= 37
while the main choosing is done by
FUNCTION randomNo (low, high)
dist = high - low + 1
lvl = INT(LOG(dist) / LOG(2) + .5)
rng r
IF r > lvl THEN
randomNo = high
ELSE
SELECT CASE r
CASE 1
randomNo = randomNo(low, low + dist / 2 - 1)
CASE 2
randomNo = randomNo(low + dist / 2, low + 3 * dist / 4 - 1)
CASE 3
randomNo = randomNo(low + 3 * dist / 4, low + 7 * dist / 8 - 1)
CASE 4
randomNo = randomNo(low + 7 * dist / 8, low + 15 * dist / 16 - 1)
CASE 5
randomNo = randomNo(low + 15 * dist / 16, low + 31 * dist / 32 - 1)
CASE 6
randomNo = randomNo(low + 31 * dist / 32, low + 63 * dist / 64 - 1)
END SELECT
END IF
END FUNCTION
In this instance the CASE 6 could have been written just to choose 63, but the code is written to be extensible to when there is the possibility of more than 64 initially, and we could then write CASE 7, etc.
The line
rng r
is the one that actually invokes the provided random number generator to place the random integer into r.
To test this out in Basic, we need to supply the rng that functions as specified, since Basic's RND() function returns a real number between zero and one, uniformly distributed. The following subroutine simulates the specified RNG:
SUB rng (x)
t = RND(1)
x = INT(LOG(1 / t) / LOG(2) + 1)
END SUB
The following program puts this all together and tests out both the rng simulator and the algorithm to produce uniform random integers from 1 to 37:
DECLARE FUNCTION randomNo! (low!, high!)
DECLARE SUB rng (x!)
DIM ct(100), ct2(37)
RANDOMIZE TIMER
' test the rng, which is the random number generator described as given
FOR i = 1 TO 1024
rng x
ct(x) = ct(x) + 1
IF x > 30 THEN ovrCt = ovrCt + 1
NEXT
PRINT : PRINT
FOR i = 1 TO 30: PRINT ct(i); : NEXT
PRINT : PRINT ovrCt
' now gen rand #s by calling the algorithm that uses this to generate
' uniformly distributed numbers between 1 and 64:
FOR i = 1 TO 37000
DO
r = randomNo(1, 64)
LOOP UNTIL r <= 37
ct2(r) = ct2(r) + 1
NEXT
PRINT : PRINT
FOR i = 1 TO 37: PRINT ct2(i); : NEXT
FUNCTION randomNo (low, high)
dist = high - low + 1
lvl = INT(LOG(dist) / LOG(2) + .5)
rng r
IF r > lvl THEN
randomNo = high
ELSE
SELECT CASE r
CASE 1
randomNo = randomNo(low, low + dist / 2 - 1)
CASE 2
randomNo = randomNo(low + dist / 2, low + 3 * dist / 4 - 1)
CASE 3
randomNo = randomNo(low + 3 * dist / 4, low + 7 * dist / 8 - 1)
CASE 4
randomNo = randomNo(low + 7 * dist / 8, low + 15 * dist / 16 - 1)
CASE 5
randomNo = randomNo(low + 15 * dist / 16, low + 31 * dist / 32 - 1)
CASE 6
randomNo = randomNo(low + 31 * dist / 32, low + 63 * dist / 64 - 1)
END SELECT
END IF
END FUNCTION
SUB rng (x)
t = RND(1)
x = INT(LOG(1 / t) / LOG(2) + 1)
END SUB
A run produced:
515 273 122 52 30 16 12 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
985 1007 937 963 1004 1044 999 1041 952 999 983 1031 1010 981 1000 1017 1040 1063 986 1006 993 998 1005 1021 989 998 947 958 1012 1003 967 1008 1010 1021 981 1019 1022
where the first set are the statistics from 1024 invocations of the simulated RNG, where 1 was expected 512 times, 2 expected 256 times, etc.
The second set came from 37,000 invocations of the 1-37 algorithm, so each number was expected 1000 times.
Edited on June 8, 2004, 3:55 pm
Edited on June 8, 2004, 3:56 pm
|
|
Posted by Charlie
on 2004-06-08 15:22:41 |
solution
