rand() between m and n

[Kai-Uwe Bux]

Hello all,
why you are going far away?
first use srand() to randomize radom number, srand get a parameter as
seed, like:
srand(3); or you can use srand(time(0));
then use this method to have randome number in a certain range:
x=minum number +rand()% maximum number;

Yes, that surely works but brings back my original comment. Using the
modulo operation you interfere with the randomness

How, and why?

and don't make use of the full period of the random generator.

Huh? I see that that can happen. However, I do not see why the
alternative of chopping [0,RAND_MAX] into n intervals of equal length it
a priory better.

Well we're getting into a hot topic here which has been discussed
extensively. On one hand using modulo you might skew the results towards
lower values

No mapping of [0,RAND_MAX+1) to [0,n) can produce truly uniform results
unless n divides RAND_MAX+1. To give correct probabilities you need to
throw away some results from rand().

and on the other hand you can have an effect on the
randomness. The reason is that the modulo operation uses low order bits
and depending on the type of random generator the high-order bits might
show better randomness. However, this is something which depends on the
implementation of rand

That's my point exactly. I do not oppose the statement that there are rand
implementations where modding is significantly worse than rescaling.

and is the subject of endless discussions! For a
thorough discussion on this including the mathematics you might refer to
Knuth's book The Art of computer programming Vol.2 and/or Numerical
Recipes.


Yes and no. Of course you will never get good results if your random
generator is crap. However, the simple scaling and offsetting does not
interfere with any property of the RNG and therefore does not affect the
"randomness".

As a general statement, this seems false: simple scaling gives preference to
high order bits. If the rand() implementation uses a random number
generator whose higher order bits are less random than its lower order
bits, rescaling is worse than taking remainders. (Rumor has it, though,
that such weakness is less common among random number generators than crapy
low-order bits

In opposition to this the modulo mapping can affect the randomness because
you're introducing a limitation.

[snip]

Best

Kai-Uwe Bux

 

[Chris Theis]

As I pointed out in another message, this doesn't compensate for
mismatched range sizes. The bias is less obvious than when using
remainainder because remainder puts the excess values down at the low end
of the target range, while the floating-point approach distributes them
more evenly. But try that code with a custom rand function that generates
values between 0 and 8, inclusive. One of the values will turn up twice as
often as the others. (I haven't done the analysis to figure out which
one.)

To avoid this bias, compute the largest multiple of the number of values
in the target range (m * (to - from + 1)) that is less than or equal to
the number of values in the generator's range (loosely, RAND_MAX+1, but
beware of overlows). Each time you call rand, check whether the value is
greater than or equal to this largest multiple; if it is, call rand again.

Hi Pete,

you're of course right about the introduction of a bias in both cases
(remainder and the floating point approach). However, I'm a bit sceptical
with respect to simply throwing away numbers above a certain threshold.
Depending on the situation (and the range) you might virtually shorten the
period of your RNG, which could introduce another problem. But I want to
emphasize that this depends very much on the situation.

There is one question that you might probably be able to answer. All RNG's
(Mersenne twister, RANMAR etc.) that we are using in the development of our
Monte Carlo simulations return values in the range from [0,1) which makes
sense from a mathematical point of view. I never quite figured why rand()
returns integer values. Probably you could shed some light on that.

Cheers
Chris

 

[Chris Theis]

Huh? I see that that can happen. However, I do not see why the
alternative
of chopping [0,RAND_MAX] into n intervals of equal length it a priory
better.

Well we're getting into a hot topic here which has been discussed
extensively. On one hand using modulo you might skew the results towards
lower values and on the other hand you can have an effect on the
randomness. The reason is that the modulo operation uses low order bits

That's not the reason. Consider a drastically simplified case: a rand()
function that produces values between 0 and 5 inclusive, and an attempt to
generate values from 0 to 4 inclusive. Using the remainder operator (C and
C++ do not have a modulus operator, but for positive arguments remainder
and modulus do the same thing), the generated value 0, 1, 2, 3, and 4 each
map to themselves, and the generated value 5 maps to 0. So you get twice
as many 0's in the output.

When you use floating point, you're still mapping six values into five
slots, and one of the slots will come up twice as often as the others. Try
it.

[SNIP]

Sorry, but I'm not quite sure I understand what you mean by "using floating
point". If you do the scaling as I've said in one of my previous posts I
very much doubt that I would get one of the slots twice as often as the
others. Running a simple program like the one below shows a (more or less)
uniform distribution. Of course this is no relevant hypothesis test for
distributions nor one of the DIE-hard tests for RNGs!

int randam(int from, int to) {
return static_cast<int>( from + ( (to - from) * (rand() / (RAND_MAX +
1.0)) ));
}

int main() {
map<int, unsigned long> Histo;
srand( 0 );
for( unsigned long i = 0; i < 10000000; ++i)
Histo[ randam( 0, 6)]++;

for( map<int, unsigned long>::iterator Iter = Histo.begin(); Iter !=
Histo.end(); ++Iter )
cout << Iter->first << ": " << Iter->second << endl;

return true;
}

Probably I missunderstood your point with respect to the statement that one
of the slots should come up twice as often.

Cheers
Chris

 

[Jerry Coffin]

[ ... ]

I need help to generate some random numbers between 2 and 8.

This has been discussed a number of times in the past. One method
that works reasonably well looks like this:

#include <stdlib.h>

int rand_lim(int limit) {
int divisor = RAND_MAX/(limit+1);
int retval;

do {
retval = rand() / divisor;
} while (retval > limit);

return retval;
}

int rand_lim(int lower, int upper) {
int range = abs(upper-lower);

return rand_lim(range) + lower;
}

This doesn't use floating point, doesn't introduce skew, and normally
uses the more significant bits of the value returned by rand(), which
are generally at least as random as the less significant bits (in
some cases they're about equal, with a linear congruential generator,
the upper bits are usually more random). Yes, in theory you _could_
create a generator in which the upper bits were inferior, (if nothing
else by simply swapping bits) but I've never actually seen such a
thing.

 

[Pete Becker]

Probably I missunderstood your point with respect to the statement that one
of the slots should come up twice as often.

That was in regard to the specific example I gave. Try it.

 

[Pete Becker]

As a general statement, this seems false: simple scaling gives preference to
high order bits. If the rand() implementation uses a random number
generator whose higher order bits are less random than its lower order
bits, rescaling is worse than taking remainders. (Rumor has it, though,
that such weakness is less common among random number generators than crapy
low-order bits

Not rumor, well established fact. Of course, it's possible that things
have changed in the twenty years or so since the usually-quoted tests
were made.

 

[Pete Becker]

There is one question that you might probably be able to answer. All RNG's
(Mersenne twister, RANMAR etc.) that we are using in the development of our
Monte Carlo simulations return values in the range from [0,1) which makes
sense from a mathematical point of view. I never quite figured why rand()
returns integer values. Probably you could shed some light on that.

It's fast and simple. And the canonical implementation of mersenne
twister also returns integer values. Floating-point math will rarely be
as fast as integer math, so when speed matters, integral random number
generators will usually be better.