random number generator

[skiing]

I am really confused on how the use of a random number generator works when using cutoff and being unbiased. Here is the code that I was given to incorporate into my rng and I am particuarly confused with what the p value does I would greatly appreciate any help.

long randint(long low, long high)
{
int s,MAX, cutoff
s=MAX/(n+1);
cutoff=s*(n+1);
while((r=rng()) >= cutoff)
;
p=r/s;
}
This is the puedocode the namespace and include was already included in the program.

[Disch]

I don't know what you're trying to do there, but it looks way more complicated than it needs to be.

If you're just looking for linear distribution of a number between two given values, it's very simple:

int randint(int low,int high)
{
  int range = high - low;  // add 1 to this to make it inclusive, see below
  return (rand() % range) + low;
}

rand() % x produces a number between [0..x). Note that x is exclusive. If you want it inclusive, you just add 1 to the range.

Ex: randint(4,6); would return either 4 or 5, but never 6. If you want it to return 6 as a possible option, then add 1 to the range.

[jsmith]

The reason for the complication is to avoid bias.

Consider an RNG that generates random numbers in the range 1..10 inclusive.

Suppose further that the user wants to generate a random number in the range 1..3 inclusive.

Now given the RNG "algorithm":

return 1 + ( rng() % 3 );

rng() returns 1..10, so the possible outcomes are:

[tt]
rng()
result 1 + ( rng() % 3 )
-------------------------------------------
1 2
2 3
3 1
4 2
5 3
6 1
7 2
8 3
9 1
10 2
--------------------------------------------

1 is returned 3/10 (30%) of the time;
2 is returned 4/10 (40%) of the time;
3 is returned 3/10 (30%) of the time.

Therefore the algorithm is biased towards 2.
Note that this happens because the last rng() value -- 10
yields the fourth 2 result.

If the rng() is zero-based, (sorry, my example isn't), then
rng() results 0...N-1 (where N is the width of the range of
numbers you want) yield an unbiased generator for your
range. That is, every rng() result maps to exactly one
value in your range. Using the modulo trick (rng() % N)
means that rng() results 0...k*N-1 is also unbiased.

The bias gets introduced when rng() can return fewer
than N values greater than k*N-1. To eliminate the bias,
you discard all rng() results greater than k*N-1. This
is the purpose of the above while() loop.

[skiing]

I understand what you are saying but what does the p value do and how do you use that to calculate the random number?

[jsmith]

Well, first you have to post syntactically correct code, otherwise I can't be
sure of the real intention of the function or if there are any other typos.
Aside from the missing semicolon on the first line of the function, MAX is
used but uninitialized; n, r, and p are used but undeclared, and the function
doesn't actually return anything.