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.

(In reply to re: Implementing Thalamus's 47-bits with Brian Smith's bit-stream. by Brian Smith)

The following implementation throws away the random binary streams that evaluate 37^9 or above:

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

maxVal = 1
FOR i = 1 TO 9   ' multiplication avoids inaccuracy of ^, which uses logs
 maxVal = maxVal * 37
NEXT

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
  DO
    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
  LOOP UNTIL stream < maxVal
  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

A run shows:

 9911  10010  9954  10125  10057  9923  10052  10099  9986  9975  9862  10021  10072  9897  10148  9998  10027  9913  10032  10125  10006  9936  9996  9929  10008  9935  9820  10116  10035  10112  10081  9956  10122  9902  10033  9951
 9875

 1069304       370000        2.890010810810811

So with this throw-away we now average 2.89 RNG calls per random 1-37.

Posted by Charlie on 2004-06-16 15:23:55