2

Given a boolean random number generator. How can I use it to generate random number in the range 0 to n.

anuj
  • 1,010
  • 2
  • 11
  • 26
  • 1
    Define "boolean random number generator" – Nir Alfasi Aug 23 '14 at 17:07
  • 2
    Generate a random number between 0 and power-of-two which is at least `n` and retry when the result is at least n. – CodesInChaos Aug 23 '14 at 17:07
  • 1
    @alfasin a "Boolean random number generator" is already well defined. – kevin Aug 23 '14 at 17:11
  • @kayson then a link would be appreciated! – Nir Alfasi Aug 23 '14 at 17:14
  • Binary numbers are also numbers. Thus a "Boolean random number generator" generates binary number, which also happens to be a Boolean at the same time. – kevin Aug 23 '14 at 17:15
  • @kayson binary number is not only 0/1: 1001 is also a binary number. Again, if it's well defined I'd appreciate a link/reference. – Nir Alfasi Aug 23 '14 at 17:56
  • @alfasin: The relationship between Boolean and numbers are generally discussed in introductory programming textbooks. – kevin Aug 23 '14 at 18:10
  • @kayson you're avoiding the original question, what's the definition of a "boolean random number generator". I'm pretty sure it's a poor choice of words because it doesn't make much sense (at least not to me). – Nir Alfasi Aug 23 '14 at 18:14
  • @alfasin: I'm sorry to hear that the term is unintuitive to you. FYI, a "Boolean random number generator" is a random number generator (RNG for short) that generate Boolean numbers randomly. Similarly, an "int32 random number generator" would generate a 32-bit integer values randomly. – kevin Aug 23 '14 at 18:21
  • @kayson like I said, `1001` is also a boolean number. According to your definition of "Boolean random number generator"- the question is redundant (any integer `n` has a binary representation) – Nir Alfasi Aug 23 '14 at 18:31
  • @alfasin: Negative. `1001` is a *binary* number, not a *Boolean* number. Again, the first chapter of most introductory programming textbooks usually address this difference. – kevin Aug 23 '14 at 18:34
  • 1
    `Boolean` and `number` are two different types. Again, can you provide a link/reference that provides a definition? saying " introductory programming textbooks" is a wave-off. Either provide reference (to such a textbook) that support your weird definition or admit that you're wrong. – Nir Alfasi Aug 23 '14 at 18:40
  • Hmmm...I'm wondering who's wrong here, seeing as you deleted your answer then requested clarification of the question due to the failure to realize that Booleans are number and the confusion between binary numbers and Boolean numbers. References to Boolean algebra (ever heard of those?) should clear up things for you, but I can't help if you require SO to provide such resources for you. – kevin Aug 23 '14 at 19:25

1 Answers1

3

Set the bits of the number one after the other. Say you use the generator 10 times. That'll give you 10 chances to have either '0' or '1' in each round. You'll now generate a random number between 0 to 1023 inclusive.

To get a random number from 0 to n you'll need to use the generator lg(n) times (lg = log base 2).

kevin
  • 2,196
  • 1
  • 20
  • 24
  • What if generating a random number between 0 and 987 (where n is not a power-of-2)? Does it preserve the random properties is simply truncating a larger generated range? – user2864740 Aug 23 '14 at 17:16
  • @user2864740 the last sentence answers that, it's ugly but should work. Not sure about the distribution of the results though. – Nir Alfasi Aug 23 '14 at 17:18
  • 1
    Then take the ceiling of the number after log. Reject the result if the number is greater than 987. This won't guarantee a result is generated, but if it does, the probability of the number from 0 to 987 is even. – kevin Aug 23 '14 at 17:18
  • In case anyone wonders, the expected number of required numbers to be generated is at most 2. – G. Bach Aug 23 '14 at 17:27