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

 Random Number Generator (Posted on 2004-06-08)
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.)
 re(2): Implementing Thalamus's 47-bits with Brian Smith's bit-stream. | Comment 25 of 26 |
(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

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)
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

 Search: Search body:
Forums (0)