RFC: clc-compliant pseudo-random number generator

[Old Wolf]

Does the Standard say that DBL_MAX must be a compile-time constant?

Yes. From C99 5.2.4.2.2:

The values given in the following list shall be replaced by
constant expressions with implementation-defined values that
are greater than or equal to those shown:

- maximum representable finite floating-point number, (1 - b-p)bemax
FLT_MAX 1E+37
DBL_MAX 1E+37
LDBL_MAX 1E+37

BCC 5.x has never made any pretense at C99 compatibility.

OTOH, BCC 6 does claim C99 compatibility.
OTOH (I need 3 hands..) BCC 6 is non-free (I think the
cheapest option is to pay $10 for a version with some restrictive licencing)

 

[Ben Pfaff]

BCC 5.x has never made any pretense at C99 compatibility.

I was planning to reply that practically the same text was in
C90, but in fact my "final draft" copy here doesn't say that
these must be constant expressions. Hmm. I'll do something else
then.

 

[CBFalconer]

BCC 5.x has never made any pretense at C99 compatibility.

The same values appear in the C89 standard. However it doesn't
appear to specify 'constant'.

 

[Ben Pfaff]

Thanks to everyone for your comments. I've revised my code and
posted it at
http://benpfaff.org/writings/clc/random.html
Further comments are welcome. I will certainly continue to
improve my code as deficiencies are pointed out. (I am
particularly uncertain whether the get_octet() function is
implemented correctly.)

Ben

 

[Peter Shaggy Haywood]

Groovy hepcat E. Robert Tisdale was jivin' on Mon, 19 Jan 2004
18:19:49 -0800 in comp.lang.c.
Re: RFC: clc-compliant pseudo-random number generator's a cool scene!
Dig it!

One issue that comes up fairly often around here is the poor
quality of the pseudo-random number generators supplied with many
C implementations. As a result, we have to recommend things like
using the high-order bits returned by rand() instead of the
low-order bits, avoiding using rand() for anything that wants
decently random numbers, not using rand() if you want more than
approx. UINT_MAX total different sequences, and so on.

So I wrote some PRNG code that uses RC4, with a seed of up to 256
bytes. Here it is. I believe it is clc-compliant.
Comments on this and anything else are welcome.

[snip]

Why is your pseudo random number generator "better" than rand()?

Please read the above exerpt. Ben explains his rationale. Then read
the FAQ. This gives greater insight into what Ben said.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?

 

[Peter Shaggy Haywood]

Groovy hepcat E. Robert Tisdale was jivin' on Mon, 19 Jan 2004
23:34:46 -0800 in comp.lang.c.
Re: RFC: clc-compliant pseudo-random number generator's a cool scene!
Dig it!

Did you include float.h?

Tisdale, can't you read for yourself? He did indeed include float.h.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?

 

[Michael Wojcik]

I was planning to reply that practically the same text was in
C90, but in fact my "final draft" copy here doesn't say that
these must be constant expressions.

Yes, the final text of 9899-1990 says:

Of the values in the <float.h> header, FLT_RADIX shall be a
constant expression suitable for use in #if preprocessing
directives; all other values need not be constant expressions.
(C90 5.2.4.2.2)

(I think I managed to quote that bit correctly.)

So unlike C99, C90 specifically allowed FLT_MAX, DBL_MAX, etc to
be non-constant expressions.

--
Michael Wojcik (e-mail address removed)

This is a "rubbering action game," a 2D platformer where you control a
girl equipped with an elastic rope with a fishing hook at the end.
-- review of _Umihara Kawase Shun_ for the Sony Playstation

 

[Hallvard B Furuseth]

http://benpfaff.org/writings/clc/random.html

get_octet (const void *bytes_, size_t n_bytes, size_t octet_idx)
(...)
return bytes[octet_idx];

return bytes[octet_idx % n_bytes];

prng_get_ulong (void)
(...)
ulng = (ulng << CHAR_BIT) | prng_get_octet ();

ulng = (ulng << 8) | prng_get_octet ();

Same in prng_get_uint().

prng_get_double (void)
{
for (;
{
double dbl = (double) prng_get_ulong () / ULONG_MAX;
if (dbl >= 0.0 && dbl < 1.0)
return dbl;

Heh. You are a lot more paranoid than me. While I can imagine dbl
could be >= 1, I cannot imagine it getting the wrong sign. OTOH,
the standard doesn't seem to forbid it...

BTW, the statement

double dbl = prng_get_ulong () / (ULONG_MAX + 1.0);

which someone suggested is slightly better even though you still need to
test that the result is less than 1.0. It does eliminate a loop once
every ULONG_MAX calls.

prng_get_double_normal (void)

Just to be _quite_ safe, you could insert

static double limit; /* guard against overflow in -2.*log(s)/s */
if (limit == 0)
limit = log(DBL_MAX/2) / (DBL_MAX/2);

before the loop, and end it with `while (s >= 1 || s < limit);'.
Otherwise the function will crash if prng_get_double() returns 0.5
or something very close to it twice in a row.

(I am particularly uncertain whether the get_octet() function is
implemented correctly.)

I #defined char as short and CHAR_BIT as 13 and inserted some asserts
and test output. Seems to be correct except for the bug above.

 

[Ben Pfaff]

Thanks for the tips. I incorporated all of them.

Just to be _quite_ safe, you could insert

static double limit; /* guard against overflow in -2.*log(s)/s */
if (limit == 0)
limit = log(DBL_MAX/2) / (DBL_MAX/2);

before the loop, and end it with `while (s >= 1 || s < limit);'.
Otherwise the function will crash if prng_get_double() returns 0.5
or something very close to it twice in a row.

This one is particularly clear-sighted.

 

[Peter Nilsson]

Thanks to everyone for your comments. I've revised my code and
posted it at
http://benpfaff.org/writings/clc/random.html
Further comments are welcome. I will certainly continue to
improve my code as deficiencies are pointed out. (I am
particularly uncertain whether the get_octet() function is
implemented correctly.)

From the link...

c |= ((unsigned) bytes[second_byte] & bits_left_mask) << bits_filled;

The (unsigned) cast is redundant in light of the mask. However, leaving in
the cast, you can remove the second mask by delaying the 0xFF mask of the
original octet component.

My first (untested) attempt was... [complete with student commentary ;-]

static unsigned char
get_octet (const void *buf, size_t nbytes, size_t ioct)
{
unsigned char octet; /* result octet */
const unsigned char *bp = buf; /* byte pointer */

if (CHAR_BIT == 8)
{
octet = bp[ioct % nbytes];
}
else
{
size_t ibit = ioct * 8u; /* raw bit index */
size_t ibyte = ibit / CHAR_BIT; /* raw byte index */

ibit %= CHAR_BIT; /* index byte's bit index */
ibyte %= nbytes; /* byte index (normalised) */

octet = bp[ibyte] >> ibit; /* [partial] octet */

/*
// Does the octet spans two bytes?
// This can't happen if CHAR_BIT is a multiple of 8.
// (I doubt some compilers would optimise out the
// redundant if without an explicit test)
*/
if (CHAR_BIT % 8 != 0 && ibit > CHAR_BIT - 8)
{
ibyte = (ibyte == nbytes) ? 0 : ibyte + 1; /* next byte */
/* complete octet */
octet |= ((unsigned) bp[ibyte]) << (CHAR_BIT - ibit);
}

octet &= 0xFF; /* mask 8 bits only */
}

return octet;
}

 

[Dan Pop]

I was planning to reply that practically the same text was in
C90, but in fact my "final draft" copy here doesn't say that
these must be constant expressions.

It *explicitly* allows them not to:

Of the values in the <float.h> header, FLT_RADIX shall be a
constant expression suitable for use in #if preprocessing directives;
all other values need not be constant expressions.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Dan