## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Random Number API - Part 2...

5 replies to this topic

### #1 Anza Power

Anza Power

Junior Member

• Members
• 80 posts

Posted 06 August 2013 - 07:01 PM

You must solve Part 1 before reading this one.

Ok so we saw that a uniform binary number generator (fair coin) isn't good for us when we want to generate stuff with probability 1/n where n isn't a power of 2.

So instead of a [0.5 , 0.5] generator, I am allowing you to customize your own random generator, namely you choose some k>1 and give me {p1...pk} and I will give you a random number generator that generates numbers between 1 and k with those probabilities.

What kind of generator do you choose and how will you use it to generate numbers with probability 1/n?

(note again I ask that your algorithm guarantee not to run for ever, as in for every n exists M such that you use the customized generator at most M times)

• 0

### #2 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 07 August 2013 - 06:36 AM

Spoiler for i think I'm on to something...

Edited by phil1882, 07 August 2013 - 06:39 AM.

• 0

### #3 witzar

witzar

• Members
• 233 posts

Posted 07 August 2013 - 01:08 PM

Spoiler for

• 0

### #4 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 07 August 2013 - 04:31 PM

Spoiler for hmmm

• 0

### #5 Anza Power

Anza Power

Junior Member

• Members
• 80 posts

Posted 07 August 2013 - 08:26 PM

Spoiler for

You're on to something but the proof isn't complete.

The limit M(n) is is different for each n, so for example it could be that for rng(3) you use your generator just once and for rng(7) you need it 1023 times.

Spoiler for my partial proof

Edited by Anza Power, 07 August 2013 - 08:34 PM.

• 0

### #6 phil1882

phil1882

Senior Member

• Members
• 564 posts

Posted 07 August 2013 - 11:58 PM

hmmm! in an interesting puzzle. is there a finite set of irrational numbers you could use to get every whole number?

i would think not. but how to prove it?

Spoiler for the problem with using irrationals

• 0

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users