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.)
 Implementing Thalamus's 47-bits with Brian Smith's bit-stream. | Comment 20 of 26 |

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

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

 Search: Search body:
Forums (0)