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.

  Submitted by Brian Smith    
Rating: 2.0000 (1 votes)
Solution: (Hide)
There are several algorithms in the comments, but the most efficient is this one which averages 2.89 RNG calls per random 1-37.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Solutionsolution, not sure if it's been posted alreadyBon2004-08-09 13:59:21
re(2): Implementing Thalamus's 47-bits with Brian Smith's bit-stream.Charlie2004-06-16 15:23:55
re(2): Implementing Thalamus's 47-bits with Brian Smith's bit-stream.Thalamus2004-06-16 14:42:14
If it even mattersBrian Smith2004-06-16 13:47:48
re: Implementing Thalamus's 47-bits with Brian Smith's bit-stream.Brian Smith2004-06-16 13:46:23
re: Implementing Thalamus's 47-bits with Brian Smith's bit-stream.Thalamus2004-06-16 11:42:17
SolutionImplementing Thalamus's 47-bits with Brian Smith's bit-stream.Charlie2004-06-16 10:33:37
re(5): solution - Charlie?Charlie2004-06-16 08:58:50
re(5): solutionBrian Smith2004-06-16 08:48:29
re(4): solution - Charlie?Thalamus2004-06-16 01:04:11
re(3): solution - Charlie?Charlie2004-06-15 20:27:24
Bit streamBrian Smith2004-06-15 15:19:29
Questionre(2): solution - Charlie?Thalamus2004-06-15 12:30:00
re: My algorithmCharlie2004-06-15 10:20:28
re: solutionCharlie2004-06-15 09:26:49
My algorithmBrian Smith2004-06-14 18:59:16
Non Elegant IdeaLarry2004-06-08 23:58:01
A faster solution than my earlier one...Erik O.2004-06-08 16:29:15
re(2): This little program doesn't do the trick...Erik O.2004-06-08 16:16:03
Some Thoughtsre: This little program doesn't do the trick...Oskar2004-06-08 15:45:42
SolutionsolutionCharlie2004-06-08 15:22:41
Some ThoughtsProgram to simulate the weird randomizerErik O.2004-06-08 14:57:00
re: program (needed some revision...)Erik O.2004-06-08 14:44:16
This little program should do the trick...Erik O.2004-06-08 14:22:25
SolutionA particularly inefficient solution!Thalamus2004-06-08 13:50:58
possible solutionMax2004-06-08 13:40:33
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 (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information