By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,454 Members | 3,103 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,454 IT Pros & Developers. It's quick & easy.

RFC: clc-compliant pseudo-random number generator

P: n/a
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.

----------------------------------------------------------------------
/*
* prng.c - Portable, ISO C90 and C99 compliant high-quality
* pseudo-random number generator based on the alleged RC4
* cipher. This PRNG should be suitable for most general-purpose
* uses. Not recommended for cryptographic or financial
* purposes. Not thread-safe.
*/

/*
* Copyright (c) 2004 Ben Pfaff <bl*@cs.stanford.edu>.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the
* following conditions are met:
*
* 1. Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
*
* 2. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
*
* 3. The author's and contributors' names may not be used to
* endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS
* IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
* SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
* OF SUCH DAMAGE.
*
*/

#include "prng.h"
#include <assert.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <time.h>

/* RC4-based pseudo-random state. */
static unsigned char s[256];
static int s_i, s_j;

/* Nonzero if PRNG has been seeded. */
static int seeded;

/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L
#define INLINE inline
#else
#define INLINE
#endif

/* Swap bytes. */
static INLINE void
swap_byte (unsigned char *a, unsigned char *b)
{
unsigned char t = *a;
*a = *b;
*b = t;
}

/* If KEY is non-null and SIZE is nonzero, seeds the
pseudo-random number generator based on the SIZE bytes in BUF.
At most the first 256 bytes of BUF are used. If KEY is a null
pointer and SIZE is zero, seeds the pseudo-random number
generator based on the current time.

If this function is not called by the user before any prng_get
function, it is called automatically to obtain a time-based
seed. */
void
prng_seed (const void *key_, size_t size)
{
const unsigned char *key = key_;
size_t key_idx;
int i, j;

assert ((key != NULL && size > 0) || (key == NULL && size == 0));

if (key == NULL)
{
static time_t t;

t = (t == 0) ? time (NULL) : t + 1;
key = (void *) &t;
size = sizeof t;
}

for (i = 0; i < 256; i++)
s[i] = i;
for (key_idx = 0, i = j = 0; i < 256; i++)
{
j = (j + s[i] + key[key_idx]) & 255;
swap_byte (s + i, s + j);
if (++key_idx >= size)
key_idx = 0;
}

s_i = s_j = 0;
seeded = 1;
}

/* Returns a pseudo-random integer in the range [0,255]. */
unsigned char
prng_get_octet (void)
{
if (!seeded)
prng_seed (NULL, 0);

s_i = (s_i + 1) & 255;
s_j = (s_j + s[s_i]) & 255;
swap_byte (s + s_i, s + s_j);

return s[(s[s_i] + s[s_j]) & 255];
}

/* Returns a pseudo-random integer in the range [0,UCHAR_MAX]. */
unsigned char
prng_get_byte (void)
{
if (UCHAR_MAX == 255)
{
/* Normal case for 8-bit bytes. */
return prng_get_octet ();
}
else
{
/* Handle oversize bytes. */
unsigned byte = prng_get_octet ();
unsigned done = 255;
while ((unsigned char) done != UCHAR_MAX)
{
byte = (byte << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
return byte;
}
}

/* Fills BUF with SIZE pseudo-random bytes. */
void
prng_get_bytes (void *buf_, size_t size)
{
unsigned char *buf;

for (buf = buf_; size-- > 0; buf++)
*buf = prng_get_byte ();
}

/* Returns a pseudo-random unsigned long in the range [0,
ULONG_MAX]. */
unsigned long
prng_get_ulong (void)
{
unsigned long ulng = prng_get_octet ();
unsigned long done = 255;

while (done != ULONG_MAX)
{
ulng = (ulng << 8) | prng_get_octet ();
done = (done << 8) | 255;
}

return ulng;
}

/* Returns a pseudo-random long in the range [0, LONG_MAX]. */
long
prng_get_long (void)
{
for (;;)
{
unsigned ulng = prng_get_ulong ();
if (ulng <= LONG_MAX)
return ulng;
}
}

/* Returns a pseudo-random unsigned int in the range [0,
UINT_MAX]. */
unsigned
prng_get_uint (void)
{
unsigned uint = prng_get_octet ();
unsigned done = 255;

while (done != UINT_MAX)
{
uint = (uint << 8) | prng_get_octet ();
done = (done << 8) | 255;
}

return uint;
}

/* Returns a pseudo-random int in the range [0, INT_MAX]. */
int
prng_get_int (void)
{
for (;;)
{
unsigned uint = prng_get_uint ();
if (uint <= INT_MAX)
return uint;
}
}

/* Returns a pseudo-random floating-point number from the uniform
distribution with range [0,1). */
double
prng_get_double (void)
{
for (;;)
{
unsigned long ulng = prng_get_ulong ();
if (ulng != ULONG_MAX)
return (double) ulng / ULONG_MAX;
}
}

/* Returns a pseudo-random floating-point number from the
distribution with mean 0 and standard deviation 1. (Multiply
the result by the desired standard deviation, then add the
desired mean.) */
double
prng_get_double_normal (void)
{
/* Knuth, _The Art of Computer Programming_, Vol. 2, 3.4.1C,
Algorithm P. */
static double next_normal = DBL_MAX;
double this_normal;

if (next_normal != DBL_MAX)
{
this_normal = next_normal;
next_normal = DBL_MAX;
}
else
{
double v1, v2, s;

do
{
double u1 = prng_get_double ();
double u2 = prng_get_double ();
v1 = 2.0 * u1 - 1.0;
v2 = 2.0 * u2 - 1.0;
s = v1 * v1 + v2 * v2;
}
while (s >= 1);

this_normal = v1 * sqrt (-2. * log (s) / s);
next_normal = v2 * sqrt (-2. * log (s) / s);
}

return this_normal;
}
----------------------------------------------------------------------
#ifndef PRNG_H_INCLUDED
#define PRNG_H_INCLUDED

#include <stddef.h>

void prng_seed (const void *, size_t);
unsigned char prng_get_octet (void);
unsigned char prng_get_byte (void);
void prng_get_bytes (void *, size_t);
unsigned long prng_get_ulong (void);
long prng_get_long (void);
unsigned prng_get_uint (void);
int prng_get_int (void);
double prng_get_double (void);
double prng_get_double_normal (void);

#endif /* prng.h */
----------------------------------------------------------------------
--
"There's only one thing that will make them stop hating you.
And that's being so good at what you do that they can't ignore you.
I told them you were the best. Now you damn well better be."
--Orson Scott Card, _Ender's Game_
Nov 14 '05 #1
Share this Question
Share on Google+
70 Replies


P: n/a
Ben Pfaff wrote:
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.


Niiice.

Q: Are you going to publish this somewhere more accessible, like
sourceforge or freshmeat?

Q: What platforms have you actually tested this on?

Q: Is there a test application lurking somewhere that you can publish?

/J
Nov 14 '05 #2

P: n/a

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@pfaff.stanford.edu...
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.


Two comments:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization
time. Estimates as to how much you need to discard varies somewhat -- I've
seen estimates of 256 - 2048 bytes.

- I believe that the defined behavior for rand() is that if it is called
without seeding, it acts as if the user did srand(1). You don't; instead,
you seed it based on time.

--
poncho
Nov 14 '05 #3

P: n/a
Johan Lindh <jo***@linkdata.getridofthis.se> writes:
Ben Pfaff wrote:
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.
Niiice.

Q: Are you going to publish this somewhere more accessible, like
sourceforge or freshmeat?


I will put it up on my webpage at benpfaff.org/writings/clc when
I am satisfied with it.
Q: What platforms have you actually tested this on?
GNU/Linux i386 only.
Q: Is there a test application lurking somewhere that you can publish?


Not yet--I have only tested it in a cursory fashion. I have not
yet decided how much testing it should receive before release, or
what sort of test routine it should be packaged with.
Suggestions are welcome.
--
Just another C hacker.
Nov 14 '05 #4

P: n/a
"Scott Fluhrer" <sf******@ix.netcom.com> writes:
"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@pfaff.stanford.edu...
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.
Two comments:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization
time. Estimates as to how much you need to discard varies somewhat -- I've
seen estimates of 256 - 2048 bytes.


I'm intentionally not trying to make it cryptographically secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.
- I believe that the defined behavior for rand() is that if it is called
without seeding, it acts as if the user did srand(1). You don't; instead,
you seed it based on time.


That's also intentional. Usually the repeatability of rand() is
a surprise to beginners. Experts who want repeatability know how
to get it. Again, maybe this should be more prominent.
--
"The fact that there is a holy war doesn't mean that one of the sides
doesn't suck - usually both do..."
--Alexander Viro
Nov 14 '05 #5

P: n/a
Just curious: why not use the mersenne twister?
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list
Nov 14 '05 #6

P: n/a
Ben Pfaff wrote:
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()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?

Nov 14 '05 #7

P: n/a
Kevin D. Quitt <KQ**********@IEEIncUNMUNG.com> writes:
Just curious: why not use the mersenne twister?


It's too complicated for my taste, and I find it difficult to
prove to myself that its code is portable. I have no reason to
believe that it is not an excellent PRNG.
--
"To get the best out of this book, I strongly recommend that you read it."
--Richard Heathfield
Nov 14 '05 #8

P: n/a
"E. Robert Tisdale" <E.**************@jpl.nasa.gov> writes:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?


I forgot to mention in my original article that I don't feel
obligated to answer questions from wackos.
Nov 14 '05 #9

P: n/a
Without casting asparagus on your effort, a paper in my archive from an
unknown source:

Most RNGs work by keeping a certain number, say k, of the most recently
generated integers, then return the next integer as a function of those
k. The initial k integers, the seeds, are assumed to be randomly
chosen, usually 32-bits. The period of the RNG is related to the number
of choices for seeds, usually 2^(32k), so to get longer periods you need
to increase k.

Probably the most common type has k=1, and needs a single seed, with
each new integer a function of the previous one. An example is this
congruential RNG, a form of which was the system RNG in VAXs for many
years:

static unsigned long x = 123456789; /* a random initial x to be */
/* assigned by the calling program */
unsigned long cong( void )
{
x = 69069 * x + 362437;
return x;
}

Simple, k=1, RNGs can perform fairly well in tests of randomness such as
those in the new version of Diehard, csis.hku.hk/~diehard but experience
has shown that better performances come from RNGs with k's ranging from
4 or 5 to as much as 4097.

Here is an example with k=5, period about 2^160, one of the fastest long
period RNGs, returns more than 120 million random 32-bit integers/second
(1.8MHz CPU), seems to pass all tests:

static unsigned long
x = 123456789,
y = 362436069,
z = 521288629,
w = 88675123,
v = 886756453;
/* replace defaults with five random seed values in calling program */
unsigned long xorshift(void)
{
unsigned long t;
t = x ^ (x>>7);
x = y;
y = z;
z = w;
w = v;
v = (v ^ (v << 6)) ^ (t ^ (t << 13));
return (y + y + 1)*v;
}
Another example has k=257, period about 2^8222. Uses a static array
Q[256] and an initial carry 'c', the Q array filled with 256 random
32-bit integers in the calling program and an initial carry c<809430660
for the multiply-with-carry operation. It is very fast and seems to
pass all tests.

static unsigned long Q[ 256 ], c = 362436;
// choose random initial c<809430660
// and 256 random 32-bit
// integers for Q[]
unsigned long MWC256(void)
{
unsigned long long t,a= 809430660LL;
static unsigned char i= 255;
t = a * Q[ ++i ] + c;
c = t >> 32;
Q[ i ] = t
return t;
}
The Mersenne Twister (check Google) is an excellent RNG, with k=624. But
it requires an elaborate C program and is slower than many RNGs that do
as well in tests, have comparable or longer periods and require only a
few lines of code.

Here is a complimentary-multiply-with-carry RNG with k=4097 and a
near-record period, more than 10^33000 times as long as that of the
Twister. (2^131104 vs. 2^19937)

static unsigned long Q[ 4096 ], c = 362436;
// choose random initial
// c<809430660 and 4096
// random 32-bit integers for Q[]
unsigned long CMWC4096( void )
{
unsigned long long t, a = 18782LL;
static unsigned long i = 4095;
unsigned long x, r = 0xfffffffe;
i = (i + 1) & 4095;
t = a * Q[ i ] + c;
c = t >> 32;
x = t + c;
if ( x < c )
{
x++;
c++;
}
Q[ i ] = r - x;
return Q[i];
}

You will find several more CMWC RNGs and comments on choice of seeds in
the May 2003 Communications of the ACM.

George Marsaglia
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list
Nov 14 '05 #10

P: n/a
In article <87************@pfaff.stanford.edu>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
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.
[Everything I don't have a comment on has been snipped]
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L
#define INLINE inline
#else
#define INLINE
#endif
It might be worth putting compiler-specific inlines into the #else here,
so that (f'rexample) GCC in C89 mode would still get GCC's inlining.
(This may affect CLC-compliance, though.)

/* Returns a pseudo-random long in the range [0, LONG_MAX]. */
long
prng_get_long (void) /* Returns a pseudo-random int in the range [0, INT_MAX]. */
int
prng_get_int (void)


How difficult would it be to get pseudo-random numbers in the ranges
[INT_MIN, INT_MAX] and [LONG_MIN, LONG_MAX]?

dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca

Would you prefer he called the OP an idiot, as some regulars do?
--Ryan Hennessy in comp.lang.c
Nov 14 '05 #11

P: n/a
dj******@csclub.uwaterloo.ca (Dave Vandervies) writes:
In article <87************@pfaff.stanford.edu>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
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.

/* Returns a pseudo-random long in the range [0, LONG_MAX]. */
long
prng_get_long (void)

/* Returns a pseudo-random int in the range [0, INT_MAX]. */
int
prng_get_int (void)


How difficult would it be to get pseudo-random numbers in the ranges
[INT_MIN, INT_MAX] and [LONG_MIN, LONG_MAX]?


Not hard, it's just that in my experience that's not often
useful.
--
"Your correction is 100% correct and 0% helpful. Well done!"
--Richard Heathfield
Nov 14 '05 #12

P: n/a
Ben Pfaff wrote:
E. Robert Tisdale writes:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?

I forgot to mention in my original article that I don't feel
obligated to answer questions from wackos.


Your PRNG is a dog isn't it Ben?

My guess is that it's so slow that there are no practical uses for it.

Nov 14 '05 #13

P: n/a
Ben Pfaff <bl*@cs.stanford.edu> writes:
"Scott Fluhrer" <sf******@ix.netcom.com> writes:

[...]
- I believe that the defined behavior for rand() is that if it is
called without seeding, it acts as if the user did srand(1). You
don't; instead, you seed it based on time.


That's also intentional. Usually the repeatability of rand() is
a surprise to beginners. Experts who want repeatability know how
to get it. Again, maybe this should be more prominent.


So it's meant to be a clc-compliant pseudo-random number generator,
not a clc-compliant implementation of rand().

Which is of course precisely what you said it was, but it occurs to me
that a decent rand() implementation would also be a nice thing to
have. If it actually caught on, we could stop giving people so much
advice about how to work around the shortcomings of typical rand()
implementations (just as soon as all existing implementations vanish,
of course).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"
Nov 14 '05 #14

P: n/a

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?


I ran some benchmarks.

On Cygwin gcc, Ben's PRNG takes 9.8 nanoseconds, whereas
the rand() provided in Cygwin takes 17.6 nanoseconds.

On LCC-Win32, Ben's PRNG takes 13.2 nanoseconds, whereas the
rand() provided takes 3.0 nanoseconds.

On BCC 5.5, Ben's PRNG does not compile, whereas the rand()
provided takes 0.95 nanoseconds.

The errors compiling Ben's PRNG were:
C:\docs\prog\c>bcc32 -c prng.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
prng.c:
Warning W8008 prng.c 135: Condition is always true in function prng_get_byte
Warning W8066 prng.c 145: Unreachable code in function prng_get_byte
Error E2063 prng.c 244: Illegal initialization in function prng_get_double_normal
*** 1 errors in Compile ***

The error was at the line:
static double next_normal = DBL_MAX;

--
Simon.
Nov 14 '05 #15

P: n/a
"Simon Biber" <ne**@ralminNOSPAM.cc> writes:
On BCC 5.5, Ben's PRNG does not compile, whereas the rand()
provided takes 0.95 nanoseconds.

The errors compiling Ben's PRNG were:
C:\docs\prog\c>bcc32 -c prng.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
prng.c:
Warning W8008 prng.c 135: Condition is always true in function prng_get_byte
Warning W8066 prng.c 145: Unreachable code in function prng_get_byte
Error E2063 prng.c 244: Illegal initialization in function prng_get_double_normal
*** 1 errors in Compile ***

The error was at the line:
static double next_normal = DBL_MAX;


Bizarre. Can this be anything other than a bug in Borland C++?
--
"I hope, some day, to learn to read.
It seems to be even harder than writing."
--Richard Heathfield
Nov 14 '05 #16

P: n/a
Simon Biber wrote:
E. Robert Tisdale wrote:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?


I ran some benchmarks.

On Cygwin gcc, Ben's PRNG takes 9.8 nanoseconds, whereas
the rand() provided in Cygwin takes 17.6 nanoseconds.

On LCC-Win32, Ben's PRNG takes 13.2 nanoseconds, whereas the
rand() provided takes 3.0 nanoseconds.

On BCC 5.5, Ben's PRNG does not compile, whereas the rand()
provided takes 0.95 nanoseconds.


Thanks Simon.

"Better" pseudo random number generators are generally slower
because they compute a larger state.
A simple pseudo random number generator like rand() is better
when all you really want to do is "mix things up" a bit.

There are other criteria for "better" PRNGs such as repeatability,
portability and uniformity.
Nov 14 '05 #17

P: n/a
Ben Pfaff wrote:
Simon Biber writes:
The error was at the line:
static double next_normal = DBL_MAX;


Bizarre. Can this be anything other than a bug in Borland C++?


Did you include float.h?

Nov 14 '05 #18

P: n/a
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
"Scott Fluhrer" <sf******@ix.netcom.com> writes:
"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@pfaff.stanford.edu...
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.
Two comments:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization
time. Estimates as to how much you need to discard varies somewhat -- I've
seen estimates of 256 - 2048 bytes.

I'm intentionally not trying to make it cryptographically secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.


Why are you not trying to make it cryptographically secure? To avoid
it being classified as a weapon by the US army? =)

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Make money fast! Don't feed it!"
- Anon
Nov 14 '05 #19

P: n/a
E. Robert Tisdale wrote:
Ben Pfaff wrote:
Simon Biber writes:
The error was at the line:
static double next_normal = DBL_MAX;


Bizarre. Can this be anything other than a bug in Borland C++?


Did you include float.h?


Can you read?

Jirka
Nov 14 '05 #20

P: n/a
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L


Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.

If you want clc-compliance, drop it.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #21

P: n/a
"E. Robert Tisdale" wrote:

Ben Pfaff wrote:
E. Robert Tisdale writes:
Why is your pseudo random number generator "better" than rand()?

Is it faster than rand()?

Have you run any performance benchmarks against rand()?

I forgot to mention in my original article that I don't feel
obligated to answer questions from wackos.


Your PRNG is a dog isn't it Ben?

My guess is that it's so slow that there are no practical uses for it.


If speed is the criterion of goodness for pseudo-
random number generators, this one should win:

#define RAND() 0

You might also be interested in my super-fast versions
of the trigonometric functions:

#define SIN(x) ( (x), 0 )
#define COS(x) ( (x), 0 )
...

.... and in my blindingly fast memory management implementation:

#define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )
#define REALLOC(ptr,bytes) ( (ptr), (bytes), 0 )
#define FREE(ptr) (void)(ptr)

--
Er*********@sun.com
Nov 14 '05 #22

P: n/a
Eric Sosman <Er*********@sun.com> scribbled the following:
"E. Robert Tisdale" wrote:
Ben Pfaff wrote:
> E. Robert Tisdale writes:
>>Why is your pseudo random number generator "better" than rand()?
>>
>>Is it faster than rand()?
>>
>>Have you run any performance benchmarks against rand()?
>
> I forgot to mention in my original article that I don't feel
> obligated to answer questions from wackos.
Your PRNG is a dog isn't it Ben?

My guess is that it's so slow that there are no practical uses for it.

If speed is the criterion of goodness for pseudo-
random number generators, this one should win: #define RAND() 0 You might also be interested in my super-fast versions
of the trigonometric functions: #define SIN(x) ( (x), 0 )
#define COS(x) ( (x), 0 )
... ... and in my blindingly fast memory management implementation: #define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )
This implementation might be blindingly fast, but it does not follow
the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )
#define REALLOC(ptr,bytes) ( (ptr), (bytes), 0 )
#define FREE(ptr) (void)(ptr)


--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Hasta la Vista, Abie!"
- Bart Simpson
Nov 14 '05 #23

P: n/a
Joona I Palaste wrote:

Eric Sosman <Er*********@sun.com> scribbled the following:
... and in my blindingly fast memory management implementation:

#define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )


This implementation might be blindingly fast, but it does not follow
the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )


Thanks for the correction; I'll issue a patch immediately.
Watch for the CERT advisory.

(Can you tell that I don't use calloc() much?)

--
Er*********@sun.com
Nov 14 '05 #24

P: n/a

In article <7f********************************@4ax.com>, Kevin D. Quitt <KQ**********@IEEIncUNMUNG.com> writes:
Without casting asparagus on your effort, a paper in my archive from an
unknown source:

Most RNGs work by keeping a certain number, say k, of the most recently
generated integers, then return the next integer as a function of those
k. ...


That's an article posted by George Marsaglia to comp.lang.c on 13 May 2003.
(I kept a copy of it as well; it's a nice piece.)

On 3 April 2003 George posted another article on CMWC (Complementary
Multiply with Carry) PRNGs which was also quite interesting.

--
Michael Wojcik mi************@microfocus.com

A coding theorist is someone who doesn't think Alice is crazy. -- John Gordon
Nov 14 '05 #25

P: n/a
Dan Pop wrote:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L


Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. (...) If you want clc-compliance, drop it.


In particular since it's only used for swap_byte(), which is
only used a few places that just as well can use

#define SWAP_BYTE(x, y) \
{ \
unsigned char tmp__SWAP_BYTE = (x); \
(x) = (y); \
(y) = tmp__SWAP_BYTE; \
}

(Yes, I know you could put do...while(0) around it so it will 'expect'
to be followed by a semicolon, but I think the while(0) gives a warning
with some compilers. There is no need to do that in this code.)

--
Hallvard
Nov 14 '05 #26

P: n/a
In message <bu**********@sunnews.cern.ch>
Da*****@cern.ch (Dan Pop) wrote:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L


Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Ok, thanks for the DeathStation programming advice.

On a more practical note, what WOULD a reasonable value for a compiler in C90
mode to set __STDC_VERSION__ to, if it wanted to set it? (One reason for
wanting to set it might be to avoid warnings about it being an undefined
identifier treated as 0 in #if).

Presumably 1990xxL would make sense, but what is "xx"? Which month was C90
published (or reached whichever stage was equivalent to 199409/199901)? I
suppose 199000L would be safe whatever.

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: +44 (0) 1223 503464
182-190 Newmarket Road Fax: +44 (0) 1223 503458
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/
Nov 14 '05 #27

P: n/a
Joona I Palaste <pa*****@cc.helsinki.fi> writes:
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
I'm intentionally not trying to make it cryptographically secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.


Why are you not trying to make it cryptographically secure? To avoid
it being classified as a weapon by the US army? =)


Because if I intend it to be cryptographically secure, then a bug
is an important security hole. If I don't, a bug just means that
the output is less random. I prefer to leave cryptography to the
cryptographers.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #28

P: n/a
Da*****@cern.ch (Dan Pop) writes:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L


Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Only an actively malicious compiler would do so. I'm not too
interested in those.
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee
Nov 14 '05 #29

P: n/a
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
Joona I Palaste <pa*****@cc.helsinki.fi> writes:
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
I'm intentionally not trying to make it cryptographically secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.
Why are you not trying to make it cryptographically secure? To avoid
it being classified as a weapon by the US army? =)

Because if I intend it to be cryptographically secure, then a bug
is an important security hole. If I don't, a bug just means that
the output is less random. I prefer to leave cryptography to the
cryptographers.


So if it happens to be cryptographically secure anyway, good for it, but
you won't be losing sleep if it doesn't?

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"This is a personnel commuter."
- Train driver in Scientific American
Nov 14 '05 #30

P: n/a
Joona I Palaste <pa*****@cc.helsinki.fi> writes:
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
Joona I Palaste <pa*****@cc.helsinki.fi> writes:
Ben Pfaff <bl*@cs.stanford.edu> scribbled the following:
I'm intentionally not trying to make it cryptographically secure.
The goal is to be a better rand() for simulations etc., not to be
useful for cryptography. My comment at the top was intended to
say that, but perhaps it should be more prominent.

Why are you not trying to make it cryptographically secure? To avoid
it being classified as a weapon by the US army? =)

Because if I intend it to be cryptographically secure, then a bug
is an important security hole. If I don't, a bug just means that
the output is less random. I prefer to leave cryptography to the
cryptographers.


So if it happens to be cryptographically secure anyway, good for it, but
you won't be losing sleep if it doesn't?


Exactly.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #31

P: n/a
It might be an idea to provide a thread_safe version: Append '_r' to
the function names and add an extra parameter (a struct containing
the current static variables). The current function names would be
an interface to it, with their own static struct.

Ben Pfaff wrote:

About prng_seed:
/* If KEY is non-null and SIZE is nonzero, seeds the
pseudo-random number generator based on the SIZE bytes in BUF.
At most the first 256 bytes of BUF are used. If KEY is a null
pointer and SIZE is zero, seeds the pseudo-random number
generator based on the current time.
I think it would be both cleaner and simpler to base the choice of
whether or not to use time() on just one parameter:

Seeds the pseudo-random number generator.
If KEY is null, the seed is based on the current time.
Otherwise, SIZE must be nonzero and the seed is based on the SIZE
bytes in KEY. At most the first 256 bytes of KEY are used.
prng_get_byte (void)
{
if (UCHAR_MAX == 255)
`#if UCHAR_MAX == 255' avoids warnings about the if() test always being
true/false.
/* Handle oversize bytes. */
unsigned byte = prng_get_octet ();
unsigned done = 255;
while ((unsigned char) done != UCHAR_MAX)
{
byte = (byte << 8) | prng_get_octet ();
done = (done << 8) | 255;
}
You don't need to shift 'done'. done++ should be a bit faster:

unsigned done = 1;
do {
byte = (byte << 8) | prng_get_octet ();
} while (++done < (CHAR_BIT+7)/8);

The same applies to prng_get_ulong() and prng_get_uint().

#if CHAR_BIT % 8 != 0, you could avoid some calls to prng_get_octet() by
saving the unused bits and use them in the next prng_get_byte() call.
(If you do, remember to reset this value in prng_seed().)
prng_get_long (void)
{
for (;;)
{
unsigned ulng = prng_get_ulong ();
if (ulng <= LONG_MAX)
return ulng;
This should be enough:

return prng_get_ulong () & LONG_MAX;

Similar for prng_get_int().
/* Returns a pseudo-random floating-point number from the uniform
distribution with range [0,1). */
double
prng_get_double (void)
{
for (;;)
{
unsigned long ulng = prng_get_ulong ();
if (ulng != ULONG_MAX)
return (double) ulng / ULONG_MAX;


This can return 1, since floating point arithmetic is not exact.

double ret = (double) prng_get_ulong () / ULONG_MAX;
if (ret < 1)
return ret;

--
Hallvard
Nov 14 '05 #32

P: n/a
Scott Fluhrer wrote:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization
time. Estimates as to how much you need to discard varies somewhat -- I've
seen estimates of 256 - 2048 bytes.


Why is that? Are the first bytes less random than later ones?
If so, prng_seed() should discard the initial output even if it's
not meant to be cryptographically secure.

--
Hallvard
Nov 14 '05 #33

P: n/a
All good feedback. Thanks Hallvard, I'll incorporate these
suggestions into the next version.
--
Here's a tip: null pointers don't have to be *dull* pointers!
Nov 14 '05 #34

P: n/a

"Hallvard B Furuseth" <h.b.furuseth(nospam)@usit.uio(nospam).no> wrote in
message news:HB**************@bombur.uio.no...
Scott Fluhrer wrote:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization time. Estimates as to how much you need to discard varies somewhat -- I've seen estimates of 256 - 2048 bytes.
Why is that? Are the first bytes less random than later ones?

Well, no. It's just that by looking at the first bytes, you can get some
hints at what the seed (key) was. In addition, if you have enough initial
outputs from related seeds, well, you can figure out what the seeds are.
If so, prng_seed() should discard the initial output even if it's
not meant to be cryptographically secure.

If you're interested in "randomness" (that is, being able to pass natural
looking statistical tests) and not cryptographical security (that is, being
able to pass any test an attacker can think of), there's no reason to
discard the initial output.

In any case, there are known tests that are able to distinguish an RC4
keystream output from random given about a Gigabyte of output (even with
discarding the initial output), and so (by cryptographical standards) this
generator is somewhat limited in any case.

--
poncho
Nov 14 '05 #35

P: n/a

"Scott Fluhrer" <sf******@ix.netcom.com> wrote in message
news:KS*******************@newsread1.news.pas.eart hlink.net...

"Hallvard B Furuseth" <h.b.furuseth(nospam)@usit.uio(nospam).no> wrote in
message news:HB**************@bombur.uio.no...
Scott Fluhrer wrote:
- Since you are using RC4, if you really want to be cryptographically
secure, you'll need to discard some part of the keystream at initialization time. Estimates as to how much you need to discard varies somewhat -- I've seen estimates of 256 - 2048 bytes.
Why is that? Are the first bytes less random than later ones?

Well, no. It's just that by looking at the first bytes, you can get some
hints at what the seed (key) was. In addition, if you have enough initial
outputs from related seeds, well, you can figure out what the seeds are.
If so, prng_seed() should discard the initial output even if it's
not meant to be cryptographically secure.

If you're interested in "randomness" (that is, being able to pass natural
looking statistical tests) and not cryptographical security (that is,

being able to pass any test an attacker can think of), Sigh, I'm being sloppy here, so I better correct myself before someone else
does. It's not literally any test, but any test that can be computed within
a limited computational time (for example, 2**64 operations, for some
definition of 'operations').
there's no reason to discard the initial output.

In any case, there are known tests that are able to distinguish an RC4
keystream output from random given about a Gigabyte of output (even with
discarding the initial output), and so (by cryptographical standards) this
generator is somewhat limited in any case.

--
poncho

Nov 14 '05 #36

P: n/a
Eric Sosman wrote:
Joona I Palaste wrote:
Eric Sosman <Er*********@sun.com> scribbled the following:
... and in my blindingly fast memory management implementation:

#define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )


This implementation might be blindingly fast, but it does not
follow the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )


Thanks for the correction; I'll issue a patch immediately.
Watch for the CERT advisory.


Are you putting those in the public domain, so that Trollsdale can
use them freely?

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #37

P: n/a
Eric Sosman <Er*********@sun.com> wrote in message news:<40***************@sun.com>...
Joona I Palaste wrote:

Eric Sosman <Er*********@sun.com> scribbled the following:
... and in my blindingly fast memory management implementation: #define MALLOC(bytes) ( (bytes), 0 )
#define CALLOC(bytes) ( (bytes), 0 )


This implementation might be blindingly fast, but it does not follow
the specification. It should be:

#define CALLOC(number, bytes) ( (number), (bytes), 0 )


Thanks for the correction; I'll issue a patch immediately.
Watch for the CERT advisory.

(Can you tell that I don't use calloc() much?)


Whilst your repairing the module, note also that [m/c/re]alloc return
void *, not int...

#define MALLOC(bytes) (bytes, (void *) 0)

Add parentheses to taste... ;)

--
Peter
Nov 14 '05 #38

P: n/a
Ben Pfaff wrote:
Kevin D. Quitt <KQ**********@IEEIncUNMUNG.com> writes:
Just curious: why not use the mersenne twister?


It's too complicated for my taste, and I find it difficult to
prove to myself that its code is portable. I have no reason to
believe that it is not an excellent PRNG.


It seems to me that Ben has done a nice job here. His PRNG passes
George Marsaglia's "diehard" test with flying colors.

http://stat.fsu.edu/pub/diehard/

(Last time I checked, my local standard rand() did _not_ pass; the
Mersenne Twister does fine).

In case you're interested, Ben, I've put a little archive of the
diehard test suite as it applies to your code at

http://www.ecn.wfu.edu/~cottrell/pfaff_prng.tgz (60Kb)

--
Allin Cottrell
Department of Economics
Wake Forest University, NC

Nov 14 '05 #39

P: n/a
Hallvard B Furuseth <h.b.furuseth(nospam)@usit.uio(nospam).no> wrote in message news:<HB**************@bombur.uio.no>...
It might be an idea to provide a thread_safe version: Append '_r' to
the function names and add an extra parameter (a struct containing
the current static variables). The current function names would be
an interface to it, with their own static struct.

Ben Pfaff wrote:

About prng_seed:
/* If KEY is non-null and SIZE is nonzero, seeds the
pseudo-random number generator based on the SIZE bytes in BUF.
At most the first 256 bytes of BUF are used. If KEY is a null
pointer and SIZE is zero, seeds the pseudo-random number
generator based on the current time.


I think it would be both cleaner and simpler to base the choice of
whether or not to use time() on just one parameter:

Seeds the pseudo-random number generator.
If KEY is null, the seed is based on the current time.
Otherwise, SIZE must be nonzero and the seed is based on the SIZE
bytes in KEY. At most the first 256 bytes of KEY are used.


Why not change the size_t SIZE parameter to unsigned and, if KEY is
null and SIZE is non zero, seed on SIZE...?

if (!key && size)
{
key = &size;
size = sizeof(size);
}

That way, there is a simple mechanism for seeding by direct integers.

--
Peter
Nov 14 '05 #40

P: n/a
"Scott Fluhrer" <sf******@ix.netcom.com> wrote in
news:KS*******************@newsread1.news.pas.eart hlink.net:

"Hallvard B Furuseth" <h.b.furuseth(nospam)@usit.uio(nospam).no> wrote
in message news:HB**************@bombur.uio.no...
Scott Fluhrer wrote:
> - Since you are using RC4, if you really want to be
> cryptographically secure, you'll need to discard some part of the
> keystream at initialization > time. Estimates as to how much you need to discard varies somewhat
> -- I've > seen estimates of 256 - 2048 bytes.


Why is that? Are the first bytes less random than later ones?

Well, no. It's just that by looking at the first bytes, you can get
some hints at what the seed (key) was. In addition, if you have
enough initial outputs from related seeds, well, you can figure out
what the seeds are.


This is true for every PRNG since they're deterministic. The question is
how hard is it given any subsequence of output given the algorithm - you
only need to determine the seed at any single point in the sequence to know
the whole sequence. Unless you're doing some behind-the-scenes magic with
the seed, I don't see how throwing away 'n' numbers helps you. Could you
explain further?

<snip>

Ian Woods
Nov 14 '05 #41

P: n/a
Peter Nilsson wrote:
About prng_seed: Why not change the size_t SIZE parameter to unsigned and, if KEY is
null and SIZE is non zero, seed on SIZE...?
(...)
That way, there is a simple mechanism for seeding by direct integers.


That _almost_ lets srand(seed) be implemented as prng_seed(0, seed).
srand(0) fails, however. So I think a prng_seed_uint() function is
needed in any case.

Also,
key = &size;
size = sizeof(size);


That does not give a repeatable sequence of pseudo-random numbers if
size has a padding bit which can be either 0 or 1. I'm afraid the
key needs to be built 'by hand':

unsigned char integer_key[sizeof size];
integer_key[0] = size;
#if UINT_MAX > UCHAR_MAX
{
int i = 1;
do {
integer_key[i++] = size >>= CHAR_BIT;
} while (i < (int)sizeof size);
}
#endif
key = &integer_key;
size = sizeof size;

The #if is necessary because `size >>= CHAR_BIT' is invalid if size only
has CHAR_BIT value bits.

--
Hallvard
Nov 14 '05 #42

P: n/a
In <05****************@tematic.com> Kevin Bracey <ke**********@tematic.com> writes:
In message <bu**********@sunnews.cern.ch>
Da*****@cern.ch (Dan Pop) wrote:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
>/* Take advantage of inlining if possible. */
>#if __STDC_VERSION__ >= 199901L


Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Ok, thanks for the DeathStation programming advice.

On a more practical note, what WOULD a reasonable value for a compiler in C90
mode to set __STDC_VERSION__ to, if it wanted to set it? (One reason for
wanting to set it might be to avoid warnings about it being an undefined
identifier treated as 0 in #if).

Presumably 1990xxL would make sense, but what is "xx"? Which month was C90
published (or reached whichever stage was equivalent to 199409/199901)? I
suppose 199000L would be safe whatever.


What if the implementor decided to include the full adoption date in
the definition of __STDC_VERSION__, so that it would become 1990mmddL?
Since there was no formal specification of the __STDC_VERSION__
macro at the time, such a decision is not a priori unreasonable.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #43

P: n/a
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
Da*****@cern.ch (Dan Pop) writes:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L
Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.


Only an actively malicious compiler would do so.


Wrong! See my previous post in the thread.
I'm not too interested in those.


Undefined behaviour is undefined behaviour in clc. Once you ignore it,
any hope of clc-compliance is gone. The standards we apply to Tisdale
must be valid for Pfaff, too.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #44

P: n/a
In message <bu**********@sunnews.cern.ch>
Da*****@cern.ch (Dan Pop) wrote:
In <05****************@tematic.com> Kevin Bracey <ke**********@tematic.com> writes:
On a more practical note, what WOULD a reasonable value for a compiler in
C90 mode to set __STDC_VERSION__ to, if it wanted to set it? (One reason
for wanting to set it might be to avoid warnings about it being an
undefined identifier treated as 0 in #if).

Presumably 1990xxL would make sense, but what is "xx"? Which month was C90
published (or reached whichever stage was equivalent to 199409/199901)? I
suppose 199000L would be safe whatever.


What if the implementor decided to include the full adoption date in
the definition of __STDC_VERSION__, so that it would become 1990mmddL?


The horse is dead, you can stop flogging now. Do you have a sensible answer
to the actual question asked?

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: +44 (0) 1223 503464
182-190 Newmarket Road Fax: +44 (0) 1223 503458
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/
Nov 14 '05 #45

P: n/a
In <ae****************@tematic.com> Kevin Bracey <ke**********@tematic.com> writes:
In message <bu**********@sunnews.cern.ch>
Da*****@cern.ch (Dan Pop) wrote:
In <05****************@tematic.com> Kevin Bracey <ke**********@tematic.com> writes:
> On a more practical note, what WOULD a reasonable value for a compiler in
> C90 mode to set __STDC_VERSION__ to, if it wanted to set it? (One reason
> for wanting to set it might be to avoid warnings about it being an
> undefined identifier treated as 0 in #if).
>
>Presumably 1990xxL would make sense, but what is "xx"? Which month was C90
>published (or reached whichever stage was equivalent to 199409/199901)? I
>suppose 199000L would be safe whatever.


What if the implementor decided to include the full adoption date in
the definition of __STDC_VERSION__, so that it would become 1990mmddL?


The horse is dead, you can stop flogging now. Do you have a sensible answer
to the actual question asked?


Methinks the actual question asked is off topic in this newsgroup.
If you need c.s.c, you should know where to find it.

BTW, wasn't I supposed to be plonked by you (due to my mental problems)?

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #46

P: n/a
Da*****@cern.ch (Dan Pop) writes:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:
Da*****@cern.ch (Dan Pop) writes:
In <87************@pfaff.stanford.edu> Ben Pfaff <bl*@cs.stanford.edu> writes:

/* Take advantage of inlining if possible. */
#if __STDC_VERSION__ >= 199901L

Any use of __STDC_VERSION__ invokes undefined behaviour in a C90
implementation. Such an implementation can use it as a magic
identifier during preprocessing (e.g. the preprocessor's nasal demon
generator ;-) or simply define it as a macro with a value greater
than 199901L.
Only an actively malicious compiler would do so.


Wrong! See my previous post in the thread.


In which you wrote:
What if the implementor decided to include the full adoption date in
the definition of __STDC_VERSION__, so that it would become 1990mmddL?
Since there was no formal specification of the __STDC_VERSION__
macro at the time, such a decision is not a priori unreasonable.


Why would the implementor do so when C95 used 199409L, C99 used
199901L, and no other standard or (as far as I know) standard
draft defined __STDC_VERSION__ at all?
--
"When in doubt, treat ``feature'' as a pejorative.
(Think of a hundred-bladed Swiss army knife.)"
--Kernighan and Plauger, _Software Tools_
Nov 14 '05 #47

P: n/a
> > On BCC 5.5, Ben's PRNG does not compile, whereas the rand()
provided takes 0.95 nanoseconds.

The errors compiling Ben's PRNG were:
C:\docs\prog\c>bcc32 -c prng.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
prng.c:
Warning W8008 prng.c 135: Condition is always true in function prng_get_byte
Warning W8066 prng.c 145: Unreachable code in function prng_get_byte
This refers to "if (UCHAR_MAX == 255)" . I prefer to use #if
for comparisons like this that can be evaluated at compile-time
(I prefer not to turn off those compiler warnings, as sometimes
they show up genuine logic errors). Obviously this is just
a matter of style, unless you have a compiler with a really bad optimizer.
Error E2063 prng.c 244: Illegal initialization in function prng_get_double_normal
*** 1 errors in Compile ***

The error was at the line:
static double next_normal = DBL_MAX;


Bizarre. Can this be anything other than a bug in Borland C++?


From float.h;
#define DBL_MAX _max_dble
extern double _RTLENTRY _EXPDATA _max_dble;

[_RTLENTRY _EXPDATA is the calling convention for linking the C runtime
library, so I would suppose that is where _max_dble lives].

LDBL_MIN, FLT_MAX, LDBL_MAX are similarly declared (although
DBL_MIN, FLT_MIN, *_EPSILON, *_MAX_EXP, etc. are #defined as constants)

I'd say the compiler error is because in C (unlike C++),
static variables must be initialized to constants. It would be easy
to modify your code to work around this.

Does the Standard say that DBL_MAX must be a compile-time constant?
Nov 14 '05 #48

P: n/a
ol*****@inspire.net.nz (Old Wolf) writes:
> On BCC 5.5, Ben's PRNG does not compile, whereas the rand()
> provided takes 0.95 nanoseconds.
>
> The errors compiling Ben's PRNG were:
> C:\docs\prog\c>bcc32 -c prng.c
> Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
> prng.c:
> Warning W8008 prng.c 135: Condition is always true in function prng_get_byte
> Warning W8066 prng.c 145: Unreachable code in function prng_get_byte
This refers to "if (UCHAR_MAX == 255)" . I prefer to use #if
for comparisons like this that can be evaluated at compile-time
(I prefer not to turn off those compiler warnings, as sometimes
they show up genuine logic errors). Obviously this is just
a matter of style, unless you have a compiler with a really bad optimizer.
#if's are ugly, so I prefer to avoid them when it's reasonable.
> Error E2063 prng.c 244: Illegal initialization in function prng_get_double_normal
> *** 1 errors in Compile ***
>
> The error was at the line:
> static double next_normal = DBL_MAX;


Bizarre. Can this be anything other than a bug in Borland C++?


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

--
Go not to Usenet for counsel, for they will say both no and yes.
Nov 14 '05 #49

P: n/a
Hallvard B Furuseth <h.b.furuseth(nospam)@usit.uio(nospam).no> wrote in message news:<HB**************@bombur.uio.no>...
Peter Nilsson wrote:
About prng_seed:

Why not change the size_t SIZE parameter to unsigned and, if KEY is
null and SIZE is non zero, seed on SIZE...?
(...)
That way, there is a simple mechanism for seeding by direct integers.


That _almost_ lets srand(seed) be implemented as prng_seed(0, seed).
srand(0) fails, however. So I think a prng_seed_uint() function is
needed in any case.

Also,
key = &size;
size = sizeof(size);


That does not give a repeatable sequence of pseudo-random numbers if
size has a padding bit which can be either 0 or 1. I'm afraid the
key needs to be built 'by hand':

unsigned char integer_key[sizeof size];
integer_key[0] = size;
#if UINT_MAX > UCHAR_MAX
{
int i = 1;
do {
integer_key[i++] = size >>= CHAR_BIT;
} while (i < (int)sizeof size);
}
#endif
key = &integer_key;
size = sizeof size;

The #if is necessary because `size >>= CHAR_BIT' is invalid if size only
has CHAR_BIT value bits.


I prefer avoid such #if-s wherever reasonably possible, as just look
ugly (IMHO).

unsigned char integer_key[sizeof size];
size_t i;

integer_key[0] = size;
for (i = 1; i < sizeof size; i++)
{
size = size >> CHAR_BIT - 1 >> 1;
integer_key[i] = size;
}

key = &integer_key;
size = sizeof integer_key;

Good compilers should optimise this.

But, I did note that time_t conversion suffers the same problem, and I
don't think that's quite as easy to fix, at least not if you want to
consider aberrant implementations.

--
Peter
Nov 14 '05 #50

70 Replies

This discussion thread is closed

Replies have been disabled for this discussion.