Databases
StackOverflow2013
Postsdbo
POHow to generate an un-biased random number within an arbitrary range using the fewest bits
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to generate an un-biased random number within an arbitrary range using the fewest bits
    primarykey
    data
    text
    <p>Because of the pigeon hole principle, you can't just use </p> <pre><code>output = min + (rand() % (int)(max - min + 1)) </code></pre> <p>to generate an unbiased, uniform, result. This <a href="https://stackoverflow.com/questions/11758809/what-is-the-optimal-algorithm-for-generating-an-unbiased-random-integer-within-a/11766794#11766794">answer</a> to a similar question provides one solution but it is highly wasteful in terms of random bits consumed.</p> <p>For example, if the random range of the source is low, then the chances of having to generate a second value from the source can be quite high. Alternative, using a larger source range is inherently wasteful too.</p> <p>While I'm sure an optimal source range size could be derived, that doesn't address the question that there may be a better algorithm, rather than optimizing this one.</p> <p>[EDIT] The my idea has been shown in the answers to produce biased results.</p> <p>An approach that occurs to me is </p> <ol> <li>Consume the minimum number of bits necessary to cover the desired range. </li> <li>If that value is outside the desired range only throw away one bit and consume one more. </li> <li>Repeat as necessary.</li> </ol>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USEoin
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to generate an un-biased random number within an arbitrary range using the fewest bits
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThe man page for `rand()` suggests something along these lines: `min + (int) (((double) rand() / (RAND_MAX + 1.0)) * (max - min + 1))`. The idea is to scale the output from `rand()` into a fraction in the range `[0, 1)`, then multiply by your range and add your minimum to get a number in the range `[min, max)`. There are probably ways to do it without resorting to slower floating point operations, but whether you want to use them will depend on your performance expectations and how complex you want to get...
      singulars
      1. POHow to generate an un-biased random number within an arbitrary range using the fewest bits
      1. UStwalberg
    2. COYour approach would lead to a non-uniform distribution of outputs.
      singulars
      1. POHow to generate an un-biased random number within an arbitrary range using the fewest bits
      1. USHenry
    3. CO`rand()` returns a fixed number of random bits, are you suggesting you would only use some of them and save the rest for later? That seems much more cumbersome than necessary, since the bits are "free". If you are worried about exhausting the bit stream (which really means you have started to repeat the "random" sequence) then you should consider a better (real?) random source.
      singulars
      1. POHow to generate an un-biased random number within an arbitrary range using the fewest bits
      1. USDwayne Towell
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload