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.

It takes an average of 2.67 calls to the RNG for each random number in the range 1-37 in this implementation of building up a 47-bit number and using that to build 9 37-digit numbers, by converting to a base-37 number and using the last 9 "digits" of the result.

DEFDBL A-Z
DECLARE FUNCTION randomNo ()
DECLARE SUB rng (x)
DIM ct(100), ct2(37)
DIM SHARED numGen, callsMade
RANDOMIZE TIMER

FOR i = 1 TO 370000
 r = randomNo
 numGen = numGen + 1
 ct2(r) = ct2(r) + 1
NEXT
PRINT : PRINT
FOR i = 1 TO 37: PRINT ct2(i); : NEXT

PRINT
PRINT callsMade, numGen, callsMade / numGen

FUNCTION randomNo
 STATIC supply, stream
 IF supply = 0 THEN
  bits = 0
  stream = 0
  DO
   rng r
   FOR i = 1 TO r - 1
     bits = bits + 1
     stream = stream * 2 + 1
     IF bits > 46 THEN EXIT FOR
   NEXT
   IF bits < 47 THEN
    stream = stream * 2
    bits = bits + 1
   END IF
  LOOP UNTIL bits > 46
  supply = 9
 END IF
 r = stream - 37 * INT(stream / 37) + 1
 stream = INT(stream / 37)
 supply = supply - 1
 randomNo = r
END FUNCTION

SUB rng (x)
 callsMade = callsMade + 1
 DO
  t = RND(1)
 LOOP UNTIL t <> 0
 x = INT(LOG(1 / t) / LOG(2) + 1)
END SUB

With test results (370,000 random numbers 1-37):

 11092  10784  11086  10110  9982  9741  9971  9914  9954  9802  9798  10075  9926  9843  9879  10029  9741  10120  9912  9938  9805  9960  10023  9810  9837  9966  9938  9839  9923  9902  9830  9892  9935  9814  9889  9782  10158

 986608        370000        2.666508108108108

showing 986,600 calls were made to the RNG to generate 370,000 random numbers between 1 and 37.

Posted by Charlie on 2004-06-16 10:33:37