Portable random number generator

[Nobody]

This is not portable (i.e does not generate the same sequence on all
platforms) as the size of unsigned long is platform-depedent.

The standard guarantees that "unsigned long" is at least 32 bits. Any
additional bits will have no effect upon the result of the above. Even a
31-bit unsigned long would produce the same result.

Addition and multiplication have the property that bit N of the result is
only affected by bits <= N of the inputs. Division/remainder by 2^N are
just shift/mask.

 

[Stefan Ram]

If you want 100% portability, you can use unsigned long (which

»Portable random number generator« can be read in two ways:

- A set of function definitions that implements a random
number generator under every C implementation.

- A set of function definitions that implements a random
number generator under every C implementation AND
for the same sequence of calls, delivers the same
sequence of random numbers.

(There are RNGs that usually deliver a different sequence of
values for the same sequence of calls even under the same C
implementation [i.e., with »srand( time( 0 ))« inbuilt or
so], so the second interpretation cannot always make sense.)

 

[Malcolm McLean]

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.

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, it's OK for most purposes (eg space invader's random
walk in a video game, testing a database query system with random
queries).

 

[Malcolm McLean]

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
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]

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]

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.

 

[Keith Thompson]

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

 

[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]

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

 

[Mark Wooding]

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]

 

[lawrence.jones]

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.

 

[lawrence.jones]

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.

 

[William Hughes]

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]

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.

 

[Nobody]

In fact, the one above is one of the worst ones.

AFAIK, it's about as good as you can get from a 32-bit LCG.

The coefficients produce a maximally periodic sequence. However, you need
to trade off the number of bits returned against the periodicity of those
bits. The lower bits all have short periods, so should really be discarded.

Using 64 bits is an improvement, but if portability is desired, you can't
assume the existence of a 64-bit integer type, so you either live with 32
bits or implement multi-word arithmetic.

FWIW, I normally use RC4 if I want something better than an LCG and I have
to implement it myself.

 

[Keith Thompson]

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.

 

[James Kanze]

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).

 

[Malcolm McLean]

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 is you don't care about randomness.

Which is generally the case. Only rarely do you need to pass
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.

 

[Nobody]

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.

Note that the only real advantage of discarding the bottom bits is to
prevent naive users from shooting themselves in the foot. If you return
the entire 32-bit state, the user can discard bits as appropriate (i.e.
they can choose to retain some of the shorter-period lower bits in order
to obtain a longer overall period).