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.)
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
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
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 (3)
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