Date: Fri, 09 Jun 2000 15:00:33 +0200 From: Teun Burgers Subject: Re: rand() comparison Sender: burgers AT ecn DOT nl To: djgpp-workers AT delorie DOT com Message-id: <3940EA71.BDD8028F@ecn.nl> Organization: Netherlands Energy Research Foundation ECN X-Envelope-to: djgpp-workers AT delorie DOT com MIME-version: 1.0 X-Mailer: Mozilla 4.51 [en] (X11; I; OSF1 V5.0 alpha) Content-type: multipart/mixed; boundary="------------461F3755A3423252B0C52980" Content-transfer-encoding: 7BIT X-Accept-Language: nl References: <200006091212 DOT IAA10758 AT delorie DOT com> Reply-To: djgpp-workers AT delorie DOT com This is a multi-part message in MIME format. --------------461F3755A3423252B0C52980 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Dieter Buerssner wrote: > > DJ Delorie wrote: > > > Could those of you with random number generator testers compare these > > generators? The first is from DJGPP, and the other two are from > > newlib. > > All three are linear congruential generators. The nth random number > is > > x_n = (x_{n-1}*a + b) % c > > where in the first case additionally the low bits are discarded. The subject of random number generators has been dealt with in depth in literature. Several generators with good sequences are known. I think they are essentially based on combining several simple linear congruential generators to get a longer sequence. The attached one is from GNU go development release 2.7.115. See http://www.fsf.org/software/gnugo/devel.html. The source has a literature reference. Perhaps Dieter can test this one also. I have another one in Fortran, based on another article. Teun -- Drs A.R. Burgers Netherlands Energy Research Foundation ECN Phone: +31-224-564959 Solar & Wind Energy, PV Cells & Modules Fax : +31-224-563214 P.O. Box 1 email: burgers AT ecn DOT nl 1755 ZG Petten, The Netherlands --------------461F3755A3423252B0C52980 Content-Type: text/plain; charset=us-ascii; name="random.c" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="random.c" /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ * This is GNU GO, a Go program. Contact gnugo AT gnu DOT org, or see * * http://www.gnu.org/software/gnugo/ for more information. * * * * Copyright 1999 and 2000 by the Free Software Foundation. * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License * * as published by the Free Software Foundation - version 2. * * * * This program is distributed in the hope that it will be * * useful, but WITHOUT ANY WARRANTY; without even the implied * * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR * * PURPOSE. See the GNU General Public License in file COPYING * * for more details. * * * * You should have received a copy of the GNU General Public * * License along with this program; if not, write to the Free * * Software Foundation, Inc., 59 Temple Place - Suite 330, * * Boston, MA 02111, USA * \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #include #include #ifdef HAVE_CONFIG_H #include #endif #include "random.h" /* This is an implementation of the TGFSR (twisted generalized * feedback shift register) random number generator TT800, which was * published in: * * Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II. * ACM Transactions on Modeling and Computer Simulations, * Vol 4, No. 3, July 1994, pp 254--266 * * The generator produces a pseudo-random sequence of 32 bit integers * with period 2^800 - 1 and is reported to have excellent * equidistribution properties, as well as being fast. */ /* Algorithm parameters. */ #define N 25 static const int m = 7; static const int s = 7; static const int t = 15; static const unsigned int a = 0x8ebfd028U; static const unsigned int b = 0x2b5b2500U; static const unsigned int c = 0xdb8b0000U; /* Global state for the random number generator. */ static unsigned int x[N]; static int k; /* Set when properly seeded. */ static int rand_initialized = 0; /* Iterate the TGFSR once to get a new state which can be used to * produce another 25 random numbers. */ static void iterate_tgfsr(void) { int i; for (i=0; i> 1) ^ ((x[i] & 1) ? a : 0); for (; i> 1) ^ ((x[i] & 1) ? a : 0); } /* Produce a random number from the next word of the internal state. */ static unsigned int next_rand(void) { int y; if (!rand_initialized) { assert(rand_initialized); /* Abort. */ gg_srand(1); /* Initialize silently if assertions disabled. */ } if (++k == N) { iterate_tgfsr(); k = 0; } y = x[k] ^ ((x[k] << s) & b); y ^= ((y << t) & c); #if (CHAR_BIT * SIZEOF_INT > 32) y &= 0xffffffffU; #endif return y; } /* Seed the random number generator. The first word of the internal * state is set by the (lower) 32 bits of seed. The remaining 24 words * are generated from the first one by a linear congruential pseudo * random generator. * * FIXME: The constants in this generator has not been checked, but * since they only are used to produce a very short sequence, which in * turn only is a seed to a stronger generator, it probably doesn't * matter much. */ void gg_srand(unsigned int seed) { int i; for (i=0; i 32) seed &= 0xffffffffU; #endif x[i] = seed; seed *= 1313; seed += 88897; } k = N-1; /* Force an immediate iteration of the TGFSR. */ rand_initialized = 1; } /* Obtain one random integer value in the interval [0, 2^31-1]. */ int gg_rand(void) { return (int) (next_rand() & 0x7fffffff); } /* Obtain one random integer value in the interval [0, 2^32-1]. */ unsigned int gg_urand(void) { return next_rand(); } /* Obtain one random floating point value in the half open interval * [0.0, 1.0). * * If the value is converted to a floating point type with less than * 32 bits mantissa (or if the double type should happen to be * unusually short), the value 1.0 may be attained. */ double gg_drand(void) { return next_rand() * 2.328306436538696e-10; } /* Retrieve the internal state of the random generator. */ void gg_get_rand_state(struct gg_rand_state *state) { int i; for (i=0; ix[i] = x[i]; state->k = k; } /* Set the internal state of the random number generator. */ void gg_set_rand_state(struct gg_rand_state *state) { int i; for (i=0; ix[i]; k = state->k; } /* * Local Variables: * tab-width: 8 * c-basic-offset: 2 * End: */ --------------461F3755A3423252B0C52980 Content-Type: text/plain; charset=us-ascii; name="random.h" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="random.h" /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ * This is GNU GO, a Go program. Contact gnugo AT gnu DOT org, or see * * http://www.gnu.org/software/gnugo/ for more information. * * * * Copyright 1999 and 2000 by the Free Software Foundation. * * * * This program is free software; you can redistribute it and/or * * modify it under the terms of the GNU General Public License * * as published by the Free Software Foundation - version 2. * * * * This program is distributed in the hope that it will be * * useful, but WITHOUT ANY WARRANTY; without even the implied * * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR * * PURPOSE. See the GNU General Public License in file COPYING * * for more details. * * * * You should have received a copy of the GNU General Public * * License along with this program; if not, write to the Free * * Software Foundation, Inc., 59 Temple Place - Suite 330, * * Boston, MA 02111, USA * \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ #ifndef _RANDOM_H_ #define _RANDOM_H_ /* This random number generator produces 32 bit unsigned integers, no * more, no less. Internally in the algorithm and for storing the * state we need a type that is at least 32 bits wide. A longer type * doesn't hurt but means a waste of bits. * * ISO C guarantees that an unsigned long always is at least 32 bits. * It is not uncommon, however, that it is longer. An unsigned int is * not guaranteed to be more than 16 bits wide, but on modern * platforms we can be certain that this type too is 32 bits (or * more). Also the GNU Coding Standards explicitly state that the * possibility of ints shorter than 32 bits should be ignored. * * We could make a typedef here to choose exactly which type to use. * In order to avoid various complications in the interface to the * random number generator, however, we prefer to consistently use * unsigned int internally and we assume this type to be at least 32 * bits wide. */ /* Internal state of the random number generator. */ struct gg_rand_state { unsigned int x[25]; /* Internal state. */ int k; /* Word counter. */ }; /* Seed the random number generator. If an unsigned int is larger than * 32 bits, only the 32 least significant bits are used for seeding. */ void gg_srand(unsigned int seed); /* Obtain one random integer value in the interval [0, 2^31-1]. */ int gg_rand(void); /* Obtain one random integer value in the interval [0, 2^32-1]. */ unsigned int gg_urand(void); /* Obtain one random floating point value in the half open interval * [0.0, 1.0). * * If the value is converted to a floating point type with less than * 32 bits mantissa (or if the double type should happen to be * unusually short), the value 1.0 may be attained. */ double gg_drand(void); /* Retrieve the internal state of the random generator. */ void gg_get_rand_state(struct gg_rand_state *state); /* Set the internal state of the random number generator. */ void gg_set_rand_state(struct gg_rand_state *state); #endif /* _RANDOM_H_ */ /* * Local Variables: * tab-width: 8 * c-basic-offset: 2 * End: */ --------------461F3755A3423252B0C52980--