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.

 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.

 Subject Author Date solution, not sure if it's been posted already Bon 2004-08-09 13:59:21 re(2): Implementing Thalamus's 47-bits with Brian Smith's bit-stream. Charlie 2004-06-16 15:23:55 re(2): Implementing Thalamus's 47-bits with Brian Smith's bit-stream. Thalamus 2004-06-16 14:42:14 If it even matters Brian Smith 2004-06-16 13:47:48 re: Implementing Thalamus's 47-bits with Brian Smith's bit-stream. Brian Smith 2004-06-16 13:46:23 re: Implementing Thalamus's 47-bits with Brian Smith's bit-stream. Thalamus 2004-06-16 11:42:17 Implementing Thalamus's 47-bits with Brian Smith's bit-stream. Charlie 2004-06-16 10:33:37 re(5): solution - Charlie? Charlie 2004-06-16 08:58:50 re(5): solution Brian Smith 2004-06-16 08:48:29 re(4): solution - Charlie? Thalamus 2004-06-16 01:04:11 re(3): solution - Charlie? Charlie 2004-06-15 20:27:24 Bit stream Brian Smith 2004-06-15 15:19:29 re(2): solution - Charlie? Thalamus 2004-06-15 12:30:00 re: My algorithm Charlie 2004-06-15 10:20:28 re: solution Charlie 2004-06-15 09:26:49 My algorithm Brian Smith 2004-06-14 18:59:16 Non Elegant Idea Larry 2004-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 re: This little program doesn't do the trick... Oskar 2004-06-08 15:45:42 solution Charlie 2004-06-08 15:22:41 Program to simulate the weird randomizer Erik 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 A particularly inefficient solution! Thalamus 2004-06-08 13:50:58 possible solution Max 2004-06-08 13:40:33

 Search: Search body:
Forums (0)