All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Random Number Generator (Posted on 2004-06-08) Difficulty: 3 of 5
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.

See The Solution Submitted by Brian Smith    
Rating: 2.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 6 of 26 |

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information