Portable random number generator
Gus Gassmann
files (some objects nest ten levels deep) and corresponding data
handling challenges. I want to do proper testing of the (C++) code and
decided that the only way to go is random tests. So now I am looking
for a random number generator with the following properties:
1. Portability.
2. Random starting points.
3. Replicability on demand.
I presume this means that I would seed the RNG based on the clock, but
keep a copy of the seed that I could optionally use at the start in
case I found a problem on a previous run.
Statistical properties are of lesser importance.
I presume I am not the first person to attempt this and am hoping to
find some guidance here. Both C and C++ would be OK for the RNG, hence
the cross-post.
Thanks for any hints.
gus
--
comp.lang.c.moderated - moderation address: cl...@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Malcolm McLean
wrote:
> So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
Just use the K and R function
static unsigned long random_seed = 123456;
void simplesrand(unsigned long seed)
{
random_seed = seed;
}
int simplerand()
{
random_seed = random_seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % 32768;
Gordon Burditt
>files (some objects nest ten levels deep) and corresponding data
>handling challenges. I want to do proper testing of the (C++) code and
>decided that the only way to go is random tests. So now I am looking
>for a random number generator with the following properties:
You're asking for a pseudo-random number generator. Software doesn't
generate true randomness on its own (except perhaps when the hardware
is failing), and to get any, it has to depend on things like
radioactive decay, keystroke timing, thermal noise, or other such
stuff. A true random number generator wouldn't have repeatability.
>1. Portability.
>2. Random starting points.
>3. Replicability on demand.
Generally, a pseudo-random number generator can be supplied a seed
as an initial input of "randomness" which may or may not be very
random. Using the same seed again will get you repeatability. Some
PRNGs will use a lot more than one integer as the initial state for
a seed. A common but rather sucky way to do this is to use the
clock. Using the time accurate to milliseconds, microseconds,
nanoseconds, etc., is unportable in C but gets you better randomness.
You might get a little more "randomness" injected by using the UNIX
process-id if you're on a platform that has one (again, this is
unportable). If your platform has /dev/random, it can use randomness
distilled from hardware actions, although this is not portable in
C.
You haven't asked for anything that the C function rand() and
associated seed function srand() seeded with the time can't do,
except that repeatability isn't guaranteed on different C implementations
by the C standard.
I recommend you try the Mersenne Twister. (See Wikipedia, which
gives a good discussion of it and some pseudocode for it.) It's
claimed to be portable, fast, has a very long period, and although
it's not cryptographically secure, it's designed for Monte Carlo
simulations. Remember, even a very good pseudo-random number
generator can be crippled by a poor choice of seed, so don't use
it for online gambling for real money or encrypting missile launch
codes.
>I presume this means that I would seed the RNG based on the clock, but
>keep a copy of the seed that I could optionally use at the start in
>case I found a problem on a previous run.
>Statistical properties are of lesser importance.
Statistical properties (although it may be difficult to predict in
advance *which* statistical properties) may prove to be important.
There might be some bugs in your code that are not uncovered if,
for example, the random numbers alternate between even and odd
numbers, which some poor PRNGs (such as some implementations of
rand() in C) are known to do.
>I presume I am not the first person to attempt this and am hoping to
>find some guidance here. Both C and C++ would be OK for the RNG, hence
>the cross-post.
Mark Wooding
> So now I am looking for a random number generator with the following
> properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
Replicability suggests a determinisic process: random starting points
are then your own problem of choosing a seed in some acceptable way.
There are a number of very simple and fast cryptographic-quality
generators out there (though you don't mention performance as being a
consideration at all).
Rivest's RC4 is extremely simple, and though it has some minor biases
seems adequate for non-cryptographic use if you can tolerate its
octet-at-a-time output.
Bernstein's Salsa20/8 is simple, fast, and seems very secure; it's also
seekable, which may or may not be of interest.
For non-cryptographic applications, I usually use Knuth's lagged
Fibonacci generator, which wants a lot of seed material; for this, I use
a linear congruential generator of my own devising.
I don't have an implementation of Salsa20/8, but you can surely find the
code online; the others are implemented in my Catacomb library, in
(pedantically) portable C:
http://git.distorted.org.uk/~mdw/catacomb/tree
available under the LGPL (see {rc4,fibrand,lc}.[ch]). Since this is for
testing purposes, I imagine the code won't in fact be distributed at all
and LGPL will therefore be acceptable. If I'm wrong about this, send me
mail: I'm willing to be generous with small portions of the library on a
case-by-case basis.
-- [mdw]
James Kanze
wrote:
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
> Statistical properties are of lesser importance.
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
There are a number of implementations available on the network;
boost has some, for example. And it's not difficult to
implement the minimum generator yourself.
With regards to the seed: time() is the classical solution, but
depending on the context in which your program runs, it may not
suffice. On Unix platforms, I'll read a couple of bytes from
/dev/random. Otherwise, munging in things like the host IP
address and the process id may be necessary to ensure
uniqueness. (And once you've got a seed, log it so you can use
it in case of problems, like you said.)
--
James Kanze
pete
>
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
>
> Thanks for any hints.
I use one here:
http://www.mindspring.com/~pfilandr/C/e_driver/
#define SEED_0 0
#define SEED_1 123456789
#define SEED_2 362436069
#define SEED_3 521288629
#define SEED_4 88675123
#define SEED_5 886756453
long unsigned seed[] = {
SEED_0, SEED_1, SEED_2, SEED_3, SEED_4, SEED_5
};
#define RAND_32LU(S) \
(S[0] = S[1] ^ S[1] >> 7, \
S[1] = S[2], \
S[2] = S[3], \
S[3] = S[4], \
S[4] = S[5], \
S[5] = (S[5] ^ S[5] << 6 \
^ S[0] ^ S[0] << 13) & 0xfffffffflu, \
S[5] * (S[2] + S[2] + 1) & 0xfffffffflu \
)
void all_different(e_type *array, size_t n, long unsigned *seed)
{
size_t i, r;
DATA(array[0]) = 0;
for (i = 1; n > i; ++i) {
r = RAND_32LU(seed) % (i + 1);
DATA(array[i]) = 0;
DATA(array[i]) = DATA(array[r]);
DATA(array[r]) = i;
}
}
--
pete
Öö Tiib
wrote:
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
>
> Thanks for any hints.
C++0x will contain a clone of boost::random. You can do pretty much
everything with that lib. All generators have their state seedable and
serializable.
Note, that random testing is very powerful tool, but common solution
there is not seedable RNG. Common solution is to automatically
extract exact minimal amount of "steps to reproduce" from noise of
(for example) 300 random operations that resulted with a problem. Then
report/store these as a problem case.
Eric Sosman
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
>
> Thanks for any hints.
The C Standard shows a portable example of a way its rand()
function could be implemented; you could take that code, change
the name, file off the serial numbers, and use it.
Depending on what you mean by "replicability," you may or may
not be able to use rand(). On any given system, rand() will be
repeatable: seed it with the same srand() argument, and you'll get
the same sequence of rand() results. But if you need to get the
same sequence on System B that you got earlier on System A, this
mightn't work: A's and B's rand() implementations may differ.
(Some people mistakenly believe that the Standard's example is *the* way
to implement rand(), but it's only an example.) So if you need
agreement across systems, you'll need to incorporate your own code
and not rely on the local rand().
--
Eric Sosman
eso...@ieee-dot-org.invalid
Dag-Erling Smørgrav
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
There are plenty of PRNGs (with the P meaning "pseudo", not "portable")
that meet those criteria. Wikipedia is a good starting point,
especially the Mersenne twister article, which includes both pseudocode
and links to existing implementations. IIUC, the Mersenne twister is
currently the best known non-cryptographic deterministic PRNG.
DES
--
Dag-Erling Smørgrav - d...@des.no
Jeff Flinn
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
I'm not sure if all of these are supported, but certainly you should
look at:
http://www.boost.org/doc/libs/1_44_0/doc/html/boost_random.html
Jeff
Francis Glassborow
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
>
> Thanks for any hints.
>
only using it for testing? And why do you need a random seed? Especially
if you need repeatability. Yes, using something like the time to
generate a seed is fine as long as you save the result so that you can
rerun it. However be warned that if your system is multi-threaded that
might not ensure repeatability.
DDD
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
>
> Thanks for any hints.
If there is no exist functions for using, why not writing yourself.
For example, by getting system time in seconds and then...
robert...@yahoo.com
wrote:
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
Err... If you don't care much about the quality of the pseudo random
numbers, why not just use the standard srand()/rand()?
robert...@yahoo.com
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
>
> Statistical properties are of lesser importance.
>
> I presume I am not the first person to attempt this and am hoping to
> find some guidance here. Both C and C++ would be OK for the RNG, hence
> the cross-post.
And if you want a generator that generates the *same* sequences across
platforms, just implement the suggested one from the C standard
(obviously you'll need to change the names):
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
christian.bau
wrote:
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
There was a huge thread about a very fast, very high quality, very
random random number generator just a few weeks ago.
Thomas Richter
> I am collaborating on a rather large project with complicated XML
> files (some objects nest ten levels deep) and corresponding data
> handling challenges. I want to do proper testing of the (C++) code and
> decided that the only way to go is random tests. So now I am looking
> for a random number generator with the following properties:
>
> 1. Portability.
> 2. Random starting points.
> 3. Replicability on demand.
>
> I presume this means that I would seed the RNG based on the clock, but
> keep a copy of the seed that I could optionally use at the start in
> case I found a problem on a previous run.
Nowadays, stdlib implementations are usually good enough to provide a
suitable random generator under the rand() function. Try that first, it
has the properties you're looking for. This is the "Ford Escort" of
random generators - sufficient for average use.
If not, please come back again.
Greetings,
Thomas
Paavo Helde
news:clcm-2010...@plethora.net:
> On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
> wrote:
>> So now I am looking
>> for a random number generator with the following properties:
>>
>> 1. Portability.
>> 2. Random starting points.
>> 3. Replicability on demand.
>>
>
>
> Just use the K and R function
>
> static unsigned long random_seed = 123456;
>
> void simplesrand(unsigned long seed)
> {
> random_seed = seed;
> }
>
> int simplerand()
> {
> random_seed = random_seed * 1103515245 +12345;
> return (unsigned int)(random_seed / 65536) % 32768;
> }
This is not portable (i.e does not generate the same sequence on all
platforms) as the size of unsigned long is platform-depedent. Use
something like uint32_t instead.
Cheers
Paavo
James Kanze
wrote:
> > So now I am looking
> > for a random number generator with the following properties:
> > 1. Portability.
> > 2. Random starting points.
> > 3. Replicability on demand.
> Just use the K and R function
> static unsigned long random_seed = 123456;
> void simplesrand(unsigned long seed)
> {
> random_seed = seed;
> }
> int simplerand()
> {
> random_seed = random_seed * 1103515245 +12345;
> return (unsigned int)(random_seed / 65536) % 32768;
> }
Have you actually tried this one? And done any statistical
analysis on the results?
--
James Kanze
steve
> Gus Gassmann <horand.gassm...@googlemail.com> writes:
> > I am collaborating on a rather large project with complicated XML
> > files (some objects nest ten levels deep) and corresponding data
> > handling challenges. I want to do proper testing of the (C++) code and
> > decided that the only way to go is random tests. So now I am looking
> > for a random number generator with the following properties:
>
> > 1. Portability.
> > 2. Random starting points.
> > 3. Replicability on demand.
>
> There are plenty of PRNGs (with the P meaning "pseudo", not "portable")
> that meet those criteria. Wikipedia is a good starting point,
> especially the Mersenne twister article, which includes both pseudocode
> and links to existing implementations. IIUC, the Mersenne twister is
> currently the best known non-cryptographic deterministic PRNG.
Google Marsaglia or see the c.l.c archive for the last month.
Also, note also that MT has some very undesirable properties.
--
steve
James Kanze
> On 11/9/2010 11:12 PM, Gus Gassmann wrote:
> The C Standard shows a portable example of a way its rand()
> function could be implemented; you could take that code,
> change the name, file off the serial numbers, and use it.
The "example" random generator in the C standard is particularly
bad.
> Depending on what you mean by "replicability," you may or may
> not be able to use rand(). On any given system, rand() will be
> repeatable: seed it with the same srand() argument, and you'll get
> the same sequence of rand() results. But if you need to get the
> same sequence on System B that you got earlier on System A, this
> mightn't work: A's and B's rand() implementations may differ.
> (Some people mistakenly believe that the Standard's example is *the* way
> to implement rand(), but it's only an example.)
And in fact, as it is (now) known to be a very poor generator,
none of the implementations I know use it.
> So if you need
> agreement across systems, you'll need to incorporate your own code
> and not rely on the local rand().
You can't rely on the local rand(), but you can easily
incorporate code from Boost or elsewhere, rather than write your
own.
--
James Kanze
Gus Gassmann
use...
For a project I am involved in I need to do some random testing. I am
looking for a random number generator with the following principles:
1. Portable. The project runs on several platforms, and I would like
to be able to support the testing on all of them. In particular,
starting from a given seed the sequence must be the same on 32-bit
and 64-bit machines.
2. Starting points must be random. I want to use an initial seed that
depends in some way on the clock.
3. Reproducibility. If I detect an error, I must be able to capture
the system state so I can reproduce the problem.
4. Simplicity. I am not looking for a fancy Mersenne twister; the
entire state of the RNG should be describable in a single seed.
Statistical properties are secondary.
I am working in C++, but a C solution would be equally useful. Any
thoughts?
Thanks
gus
Keith Thompson
> Malcolm McLean <malcolm...@btinternet.com> wrote in
> news:clcm-2010...@plethora.net:
>> On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
>> wrote:
>>> So now I am looking
>>> for a random number generator with the following properties:
>>>
>>> 1. Portability.
>>> 2. Random starting points.
>>> 3. Replicability on demand.
>>>
>>
>>
>> Just use the K and R function
>>
>> static unsigned long random_seed = 123456;
>>
>> void simplesrand(unsigned long seed)
>> {
>> random_seed = seed;
>> }
>>
>> int simplerand()
>> {
>> random_seed = random_seed * 1103515245 +12345;
>> return (unsigned int)(random_seed / 65536) % 32768;
>> }
>
> This is not portable (i.e does not generate the same sequence on all
> platforms) as the size of unsigned long is platform-depedent. Use
> something like uint32_t instead.
Strictly speaking, uint32_t isn't portable. It's new in C99,
so older implementations may not support it (it's likely that
Microsoft doesn't), though you can define it yourself. And it may
not exist at all if the system doesn't happen to support a type
with the required characteristics; for example, I've worked on a
system that had no 32-bit integer type at all.
If you want 100% portability, you can use unsigned long (which
is guaranteed to be *at least* 32 bits) along with some explicit
masking to keep results in the range 0..2**31-1. Or you can use
uint_least32_t if you know you have C99 support.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
news
>> static unsigned long random_seed = 123456;
>>
>> void simplesrand(unsigned long seed)
>> {
>> random_seed = seed;
>> }
>>
>> int simplerand()
>> {
>> random_seed = random_seed * 1103515245 +12345;
>> return (unsigned int)(random_seed / 65536) % 32768;
>> }
>
> This is not portable (i.e does not generate the same sequence on all
> platforms) as the size of unsigned long is platform-depedent. Use
> something like uint32_t instead.
It will only return differing results if unsigned int has less than
31 bits in the target architecture. What are the odds he is going to
use the program in such an environment?
lawrenc...@siemens.com
>
> The "example" random generator in the C standard is particularly
> bad.
> And in fact, as it is (now) known to be a very poor generator,
> none of the implementations I know use it.
No, it's not. It's a perfectly good 15-bit linear congruential
generator. Certainly there are other forms of generators that are
"better" by some measures, but as LCGs go, it's a decent one. A number
of implementations use it verbatim.
--
Larry Jones
In a minute, you and I are going to settle this out of doors. -- Calvin
news
> I presume this should be a FAQ, but I have not found much that is of
> use...
>
> For a project I am involved in I need to do some random testing. I am
> looking for a random number generator with the following principles:
>
> 1. Portable. The project runs on several platforms, and I would like
> to be able to support the testing on all of them. In particular,
> starting from a given seed the sequence must be the same on 32-bit
> and 64-bit machines.
> 2. Starting points must be random. I want to use an initial seed that
> depends in some way on the clock.
> 3. Reproducibility. If I detect an error, I must be able to capture
> the system state so I can reproduce the problem.
> 4. Simplicity. I am not looking for a fancy Mersenne twister; the
> entire state of the RNG should be describable in a single seed.
> Statistical properties are secondary.
>
> I am working in C++, but a C solution would be equally useful. Any
> thoughts?
You know, there is this thing called Google...
(And finding such RNGs isn't specially hard with it.)
news
>> int simplerand()
>> {
>> random_seed = random_seed * 1103515245 +12345;
>> return (unsigned int)(random_seed / 65536) % 32768;
>> }
>
> Have you actually tried this one? And done any statistical
> analysis on the results?
Since it's a linear congruential generator, there's little need to
do much statistical analysis: It's rather poor.
(Although, admittedly, not all LCG's are equally poor. Some are way
poorer than others, if the literals are chosen inappropriately. However,
even the best LCG's are rather poor compared to more robust RNG's.)
Paavo Helde
@plethora.net:
> In comp.lang.c++ Paavo Helde <myfir...@osa.pri.ee> wrote:
>>> static unsigned long random_seed = 123456;
>>>
>>> void simplesrand(unsigned long seed)
>>> {
>>> random_seed = seed;
>>> }
>>>
>>> int simplerand()
>>> {
>>> random_seed = random_seed * 1103515245 +12345;
>>> return (unsigned int)(random_seed / 65536) % 32768;
>>> }
>>
>> This is not portable (i.e does not generate the same sequence on all
>> platforms) as the size of unsigned long is platform-depedent. Use
>> something like uint32_t instead.
>
> It will only return differing results if unsigned int has less than
> 31 bits in the target architecture. What are the odds he is going to
> use the program in such an environment?
Yes, you are right, this algorithm is indifferent about what happens in
higher bits in random_seed. I have had a bad experience with another
"simple" RND which broke up in the 64-bit transition and which similarly
used overflowing unsigned long accumulators, so I thought the behavior
might be flawed in a similar way.
James Kanze
> In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
> > The "example" random generator in the C standard is particularly
> > bad.
> [...]
> > And in fact, as it is (now) known to be a very poor generator,
> > none of the implementations I know use it.
> No, it's not. It's a perfectly good 15-bit linear congruential
> generator. Certainly there are other forms of generators that are
> "better" by some measures, but as LCGs go, it's a decent one. A number
> of implementations use it verbatim.
I'm sorry, but it fails just about every known test. To begin
with, the results alternate between even and odd. The fact that
some implementations use it verbatim doesn't say much for the
quality of those implementations.
--
James Kanze
Eric Sosman
> I presume this should be a FAQ, but I have not found much that is of
> use...
>
> For a project I am involved in I need to do some random testing. I am
> looking for a random number generator with the following principles:
> I am working in C++, but a C solution would be equally useful. Any
> thoughts?
My first thought is that you haven't explained why you weren't
satisfied with the answers you got the first time you asked this
exact same question. My second thought is to refer you to those
same answers. My third thought is that I'd really be unhappy if
the same question from the same questioner popped up a third time.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Malcolm McLean
> On Nov 12, 11:05 pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
> wrote:
>
>
>
> > On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
> > wrote:
> > > So now I am looking
> > > for a random number generator with the following properties:
> > > 1. Portability.
> > > 2. Random starting points.
> > > 3. Replicability on demand.
> > Just use the K and R function
> > static unsigned long random_seed = 123456;
> > void simplesrand(unsigned long seed)
> > {
> > random_seed = seed;
> > }
> > int simplerand()
> > {
> > random_seed = random_seed * 1103515245 +12345;
> > return (unsigned int)(random_seed / 65536) % 32768;
> > }
>
> Have you actually tried this one? And done any statistical
> analysis on the results?
>
digit integers
97
20
60
30
91
47
65
89
8
76
0
25
60
85
25
50
45
4
49
97
9
73
10
70
44
36
62
93
44
2
76
59
98
80
75
20
61
9
2
40
5
5
37
38
4
81
5
52
28
16
14
48
64
64
37
68
94
20
4
55
0
79
37
23
57
61
41
30
86
96
9
32
5
98
90
83
7
63
81
24
32
22
62
1
75
60
17
11
54
4
11
93
47
94
97
18
92
22
57
3
as you can see, they are perfectly OK for many uses, eg random walks
for space invaders, or generating random queries to test a database
function.
James Kanze
> In comp.lang.c++ James Kanze <james.ka...@gmail.com> wrote:
> >> int simplerand()
> >> {
> >> random_seed = random_seed * 1103515245 +12345;
> >> return (unsigned int)(random_seed / 65536) % 32768;
> >> }
> > Have you actually tried this one? And done any statistical
> > analysis on the results?
> Since it's a linear congruential generator, there's little need to
> do much statistical analysis: It's rather poor.
Or at least, it has weaknesses, and better generators are
available. Still, a good linear congruential generator is
sufficient for many applications, and has the advantage of
simplicity and speed.
> (Although, admittedly, not all LCG's are equally poor. Some
> are way poorer than others, if the literals are chosen
> inappropriately. However, even the best LCG's are rather poor
> compared to more robust RNG's.)
In fact, the one above is one of the worst ones.
If you have 64 bit arithmetic, something like:
int32_t seed;
int random()
{
seed = (48271LL * seed) % 2147483647LL;
return seed;
}
works reasonably well (but as you say, better algorithms exist).
--
James Kanze
Malcolm McLean
> wrote:
>
>
>
> > On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
> > wrote:
> > > So now I am looking
> > > for a random number generator with the following properties:
> > > 1. Portability.
> > > 2. Random starting points.
> > > 3. Replicability on demand.
> > Just use the K and R function
> > static unsigned long random_seed = 123456;
> > void simplesrand(unsigned long seed)
> > {
> > random_seed = seed;
> > }
> > int simplerand()
> > {
> > random_seed = random_seed * 1103515245 +12345;
> > return (unsigned int)(random_seed / 65536) % 32768;
> > }
>
> Have you actually tried this one? And done any statistical
> analysis on the results?
>
random number.
As you can see, it's OK for most purposes (eg space invader's random
walk in a video game, testing a database query system with random
queries).
Keith Thompson
> On Nov 16, 2:25 am, lawrence.jo...@siemens.com wrote:
>> In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
>> > The "example" random generator in the C standard is particularly
>> > bad.
>> [...]
>> > And in fact, as it is (now) known to be a very poor generator,
>> > none of the implementations I know use it.
>
>> No, it's not. It's a perfectly good 15-bit linear congruential
>> generator. Certainly there are other forms of generators that are
>> "better" by some measures, but as LCGs go, it's a decent one. A number
>> of implementations use it verbatim.
>
> I'm sorry, but it fails just about every known test. To begin
> with, the results alternate between even and odd. The fact that
> some implementations use it verbatim doesn't say much for the
> quality of those implementations.
I've seen PRNGs whose results alternate even and odd, but the
sample implementation in the standard isn't one of them. (BTW,
the C90 and C99 standards have the same sample implementation).
Here's a sample program:
#include <stdio.h>
/*
* Copy of the sample srand()/rand() implementation from the C standard.
*/
static unsigned long int next = 1;
int my_rand(void) {
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
int main(void)
{
int i;
for (i = 0; i < 10; i ++) {
int r = my_rand();
printf("%-5s %5d\n", r % 2 == 0 ? "even" : "ODD", r);
}
return 0;
}
And here's the output I get:
even 16838
even 5758
ODD 10113
ODD 17515
ODD 31051
ODD 5627
even 23010
ODD 7419
even 16212
even 4086
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Hans-Bernhard Bröker
> Here's the result of the first 100 runs, using %100 to get a 2 digit
> random number.
> As you can see, it's OK for most purposes (eg space invader's random
> walk in a video game, testing a database query system with random
> queries).
To your benefit, we'll all assume you've been joking. Badly, bud still
joking.
Dag-Erling Smørgrav
> James Kanze <james...@gmail.com> wrote:
> > Have you actually tried this one? And done any statistical
> > analysis on the results?
> Here's the result of the first 100 runs, using %100 to get a 2 digit
> random number.
In other words, "no". And don't use modulo.
DES
--
Dag-Erling Smørgrav - d...@des.no
pete
>
> On Nov 16, 2:25 am, lawrence.jo...@siemens.com wrote:
> > In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
> > > The "example" random generator in the C standard is particularly
> > > bad.
> > [...]
> > > And in fact, as it is (now) known to be a very poor generator,
> > > none of the implementations I know use it.
>
> > No, it's not. It's a perfectly good 15-bit linear congruential
> > generator. Certainly there are other forms of generators that are
> > "better" by some measures, but as LCGs go, it's a decent one.
> > A number
> > of implementations use it verbatim.
>
> I'm sorry, but it fails just about every known test. To begin
> with, the results alternate between even and odd.
The results do not alternate between odd and even.
/* BEGIN new.c output */
16838
5758
10113
17515
31051
5627
23010
7419
16212
4086
2749
12767
9084
12060
32225
17543
25089
21183
25137
25566
/* END new.c output */
/* BEGIN new.c */
#include <stdio.h>
static unsigned long int next = 1;
int rands(void) /* RAND_MAX assumed to be 32767 */
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
int main(void)
{
int x;
puts("/* BEGIN new.c output */");
for (x = 0; 20 > x; ++x) {
printf("%d\n", rands());
}
puts("/* END new.c output */");
return 0;
}
/* END new.c */
--
pete
Mark Wooding
> On Nov 16, 2:25 am, lawrence.jo...@siemens.com wrote:
> > In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
> > > The "example" random generator in the C standard is particularly
> > > bad.
> >
> > No, it's not. It's a perfectly good 15-bit linear congruential
> > generator.
>
> I'm sorry, but it fails just about every known test. To begin
> with, the results alternate between even and odd.
This is simply false. You may have missed the division in the output
stage.
-- [mdw]
lawrenc...@siemens.com
>
> int32_t seed;
>
> int random()
> {
> seed = (48271LL * seed) % 2147483647LL;
> return seed;
> }
>
> works reasonably well (but as you say, better algorithms exist).
If your definition of "reasonably well" includes always returning 0.
--
Larry Jones
I think we need to change the rules. -- Calvin
lawrenc...@siemens.com
> with, the results alternate between even and odd.
No it doesn't. The code again from the C standard is:
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
Note the "/65536" in the return line that yields the high-order 15 bits
of the result, not the low-order. You're thinking of the brain-damaged
variant that originated at Berkeley (and apparently lives on in glibc)
that increases the range to 31 bits by eliminating the division and
increasing the modulus. That *does* fail just about every known test
and is infamously bad. Please don't tar the version in the Standard
with the same brush.
--
Larry Jones
Monopoly is more fun when you make your own Chance cards. -- Calvin
William Hughes
> On Nov 16, 2:25 am, lawrence.jo...@siemens.com wrote:
>
> > In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
> > > The "example" random generator in the C standard is particularly
> > > bad.
> > [...]
> > > And in fact, as it is (now) known to be a very poor generator,
> > > none of the implementations I know use it.
> > No, it's not. It's a perfectly good 15-bit linear congruential
> > generator. Certainly there are other forms of generators that are
> > "better" by some measures, but as LCGs go, it's a decent one. A number
> > of implementations use it verbatim.
>
> I'm sorry, but it fails just about every known test. To begin
> with, the results alternate between even and odd.
No they don't.
- William Hughes
James Kanze
> > On Nov 12, 11:05 pm, Malcolm McLean <malcolm.mcle...@btinternet.com>
> > wrote:
> > > On Nov 10, 6:12 am, Gus Gassmann <horand.gassm...@googlemail.com>
> > > wrote:
> > > > So now I am looking
> > > > for a random number generator with the following properties:
> > > > 1. Portability.
> > > > 2. Random starting points.
> > > > 3. Replicability on demand.
> > > Just use the K and R function
> > > static unsigned long random_seed = 123456;
> > > void simplesrand(unsigned long seed)
> > > {
> > > random_seed = seed;
> > > }
> > > int simplerand()
> > > {
> > > random_seed = random_seed * 1103515245 +12345;
> > > return (unsigned int)(random_seed / 65536) % 32768;
> > > }
> > Have you actually tried this one? And done any statistical
> > analysis on the results?
> Here are 100 results, created by taking modulus 100 to generate 2
> digit integers
[...]
> as you can see,
No, I can't see. Pseudo-)randomness isn't superficially
visible. What results do you get from a Chi-Square test, for
example?
> they are perfectly OK for many uses, eg random walks for space
> invaders, or generating random queries to test a database
> function.
They are perfectly OK is you don't care about randomness.
--
James Kanze
James Kanze
> In comp.lang.c.moderated James Kanze <james.ka...@gmail.com> wrote:
> > If you have 64 bit arithmetic, something like:
> > int32_t seed;
> > int random()
> > {
> > seed = (48271LL * seed) % 2147483647LL;
> > return seed;
> > }
> > works reasonably well (but as you say, better algorithms exist).
> If your definition of "reasonably well" includes always returning 0.
OK. Works reasonable well if seeded. (And you should probably
subtract 1 from the returned value.) I did say "something like"
(since I didn't have the exact code at hand, just the critical
constants).
--
James Kanze
Malcolm McLean
>
> > as you can see,
>
> No, I can't see. Pseudo-)randomness isn't superficially
> visible. What results do you get from a Chi-Square test, for
> example?
>
> > they are perfectly OK for many uses, eg random walks for space
> > invaders, or generating random queries to test a database
> > function.
>
> They are perfectly OK is you don't care about randomness.
>
sophisticated or even not-so sophisticated statistical tests for
randomness. As long as no integers are avoided and the results look
random to a superficial glance, it's probably good enough.
Keith Thompson
> In comp.lang.c.moderated James Kanze <james...@gmail.com> wrote:
>>
>> I'm sorry, but it fails just about every known test. To begin
>> with, the results alternate between even and odd.
>
> No it doesn't. The code again from the C standard is:
>
> static unsigned long int next = 1;
>
> int rand(void) // RAND_MAX assumed to be 32767
> {
> next = next * 1103515245 + 12345;
> return (unsigned int)(next/65536) % 32768;
> }
>
> Note the "/65536" in the return line that yields the high-order 15 bits
> of the result, not the low-order. You're thinking of the brain-damaged
> variant that originated at Berkeley (and apparently lives on in glibc)
> that increases the range to 31 bits by eliminating the division and
> increasing the modulus. That *does* fail just about every known test
> and is infamously bad. Please don't tar the version in the Standard
> with the same brush.
Yes, glibc still has a PRNG whose results alternate odd and even,
but that algorithm isn't the one that's use by default. You can
force its use by calling the non-standard initstate() function with
a sufficiently small state buffer.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"