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.)
Solution 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)
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
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 (1)
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