becmug@ernie.Berkeley.EDU (BECMUG Guests) (02/10/88)
I've just learned C, and am thinking of good ways to generate random numbers. Does anyone have any suggestions? Thanks, --craig latta.
lamonts@Sds.Sdsc.EDU (Steve Lamont) (02/10/88)
BECMUG Guests <becmug@ernie.Berkeley.EDU> says > I've just learned C, and am thinking of good ways to generate random > numbers. Does anyone have any suggestions? Try the function rand(). For example: ... int rand_no; rand_no = rand(); ... spl ---------------------------------------- Internet: LAMONTS@SDS.SDSC.EDU Bitnet: LAMONTS@SDSC Span: SDSC::LAMONTS (27.1) USPS: Steve Lamont San Diego Supercomputer Center P.O. Box 85608 San Diego, CA 92138 AT&T: 619.534.5126
pardo@june.cs.washington.edu (David Keppel) (02/11/88)
[ random numbers from C ? ]
On 4BSD, in addition to "rand()", there is "random()" which has enough
extra randomness to be worth looking at. (This is certainly available
on ucbernie!)
;-D on ( Random numbers base 1: 0 0 0 0 0 0 0 0 0 ... ) Pardogwyn@brl-smoke.ARPA (Doug Gwyn ) (02/11/88)
In article <22926@ucbvax.BERKELEY.EDU> becmug@ernie.Berkeley.EDU (BECMUG Guests) writes: > I've just learned C, and am thinking of good ways to generate random >numbers. Does anyone have any suggestions? Start by reading Donald Knuth's "The Art of Computer Programming, Vol. 2: Seminumerical Algorithms", Chapter 3 (Random Numbers). Until you basically understand this material, you're probably best off by simply using the pseudo-random number generator in your C library (usually called rand(), sometimes random(); on System V drand48() is pretty good). There are a few good algorithms in the professional literature and a bunch of not-so-good ones. The main moral to be drawn from Knuth is: if you really need good randomness properties, you had better thoroughly test whatever generator you're considering. All that said, here's a typical (portable) linear-congruential pseudo-random number generator, taken from the draft ANSI C standard; rand() returns an integer uniformly distributed from 0 through 32767 (inclusive), and srand() is used to initialize a sequence to a particular seed, or to avoid getting a predictable sequence (by setting a seed based on some system variable such as process ID or time-of-day). static unsigned long int next = 1; int rand(void) { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; } void srand(unsigned int seed) { next = seed; }
Uly@cup.portal.com (02/11/88)
Here's my favorite random number generator. It's Knuth's algorithm A
from Seminumerical Algorithms. The primary advantage is speed over
the linear congruential methods. The primary disadvantage is that
as of 1981 (correct me if I'm out of date) the theoretical underpinnings
for this technique were not well-understood. In any case, I use this
routine constantly and have never had a problem with it. The initializing
routine can use any 55 int array, I normally preset it with known values
and change only the first word based on the current clock ticks. Note
that the array must possess at least one odd integer. The period of this
generator is guaranteed to be at least 2^55-1.
Uly
----------------------------------------------------------------------------
Michael Hill, Hill SoftSystems | "Millions long for immortality who don't
4616 N. 16th, Arlington VA 22207| don't know what to do on a rainy Sunday
(703) 525-2353 | afternoon." -- Susan Ertz
ARPA: Uly@cup.portal.com | USENET: uunet!portal!cup!Uly
----------------------------------------------------------------------------
(Apologies for weak c code, I invariably code this one in assembler)
static int Y[55],K,J;
initrandom(seed)
int *seed;
{ int i=55;
while(i--) Y[i]= *seed++;
Y[0]=13; /* array must have one odd val */
J=23;
K=54;
}
random(maxval) /* Return psuedorandom val mod maxval */
int maxval;
{ maxval= (Y[K--]+=Y[J--])%maxval;
if(J<0) J=54;
if(K<0) K=54;
if(maxval<0) return -maxval;
return maxval;
}
...............hicks@walker-emh.arpa (Gregory Hicks COMFLEACTS) (02/24/88)
----BEGINNING OF FORWARDED MESSAGES----
Received: from DECWRL.DEC.COM by WALKER-EMH.ARPA ; 24 Feb 88 05:33:39 GMT
Received: by decwrl.dec.com (5.54.4/4.7.34)
id AA11545; Tue, 23 Feb 88 08:59:26 PST
Message-Id: <8802231659.AA11545@decwrl.dec.com>
From: dantowitz%eagle1.DEC@decwrl.dec.com (David)
Date: 23 Feb 88 11:38
To: hicks@walker-emh.ARPA
Subject: Random numbers ...
In using the random number generator below the value returned by
Rand is an integer, BUT, it should be treated as the numerator of a
fraction with a divisor of 32768!!!!
So, let X = Rand ()/32768; (a floating point value)
Now 0 <= X < 1.
To get a random number from 0 to Y-1 multiply each element of the
equation by Y, which yields:
0 <= X*Y < Y.
So your random number is REALLY:
Rand() * Y
----------
32768
If you want 1 random bit DO NOT use the low bit returned by Rand!
Use the high bit!!
To get a random number of 1 bit what you are really doing is using
a value of 2 for Y, so you get:
Rand()*2
--------
32768
This is basically the high bit of Rand. The same holds if you want
2 random bits. Use the High bits.
The MOST random bits are the high bits. The low bits follow a short
loop and for most purposes are NOT sufficiently random for ANY
application.
On 32-bit systems I have seen a variation on the Rand function
below. The system I remember most recently returned the low 31 bits
that resulted from the multiply operation.
Be sure to read the documentation for the Rand function in your
library and note the range of values it returns (to be sure that
you have the correct denominator).
Remember that although the documentation says the numbers are "random",
the low-bits are NOT "random" at all.
Be careful who you trust when someone gives you a random number
generator. They tend to be passed down from "generation" to
"generation" without anyone checking the validity of the generator.
Knuth is a good source of information for this stuff.
David Dantowitz
static unsigned long int next = 1;
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
}
----END OF FORWARDED MESSAGES----crowl@cs.rochester.edu (Lawrence Crowl) (02/25/88)
Most of my need for random numbers comes in the form of a random integer modulo
some application specific value. A lot of random number generators return
either a floating value, or some integer within the complete range of integers,
which I must then hack at to get it within the range of integers that I want.
Rather than do this all the time, I wrote a random number generator which
accepts the modulus and does the modulo calculations internally. Here is the
result of that effort. On a Sun 2/170, the 16-bit version takes 54 micro-
seconds and the 32-bit version takes 158 micro-seconds.
/*-------------------------------------------------------------------- random.c
This program contains a linear congruential pseudo-random number generator.
Each random number generation takes a parameter, modulus, and returns a
pseudo-random number in the range 0 ... modulus-1. The pseudo-random number
is taken from the high-order bits of the seed. Because twos complement
integers have more negative values than positive, this generator uses the
negative of the absolute value for some operations.
If the modulus is constant, an macro implementation of this generator will
eliminate a division. In addition, the modulus parameter is evaluated only
once, so it will have no undue side effects.
This file contains two versions of the generator, one for 16-bit twos
complement arithmentic, and one for 32-bit twos complement arithmetic.
Lawrence Crowl
University of Rochester
Computer Science Department
Rochester, New York, 14627
*/
/*----------------------------------------------------------------------- tools
Note that since the parameter to NEGABS is evaluated more than once, the
actual argument should have no side effects.
*/
#define NEGABS( i ) ((i) > 0 ? -(i) : (i))
/*-------------------------------------------------------------- 16-bit version
This version assumes that shorts are 16 bits. This allows the code to run
on machines with 32-bit ints but 16-bit hardware, such as the 68000. The
extensive casting allows reasonable compilers to generate 16-bit multiply
instructions.
The coefficients for the generator are from Peter Grogono, "Programming in
Pascal", Section 4.5, Addison-Wesley Publishing Company, 1978. I do not
know if these coefficients have been tested.
*/
static short seed16 ;
void rand16seed( seed )
short seed ;
{
seed16 = seed ;
}
short rand16mod( modulus )
short modulus ;
{
seed16 = (short)(seed16 * 25173) + 13849 ;
return (short)NEGABS(seed16) / (short)(-32768 / modulus) ;
}
/*-------------------------------------------------------------- 32-bit version
This version assumes that ints are 32 bits.
The coefficients for the generator are from David Dantowitz in article
<11972@brl-adm.ARPA> of the comp.lang.c news group. I do not know if
these coefficients have been tested.
*/
static int seed32 ;
void rand32seed( seed )
int seed ;
{
seed32 = seed ;
}
int rand32mod( modulus )
int modulus ;
{
seed32 = (seed32 * 1103515245) + 13849 ;
return NEGABS(seed32) / (-2147483648 / modulus) ;
}
/*------------------------------------------------- demonstration program
This is not a test program. For test procedures, see Donald E. Knuth,
"The Art of Computer Programming", Chaper 3, Volume 2, Second Edition,
Addison-Wesley Publishing Company, 1981
*/
#include <stdio.h>
#include <sys/time.h>
#define ITERATIONS 1000000
void main( )
{
int i, j ;
struct timeval t1, t2, t3 ;
long d1, d2 ;
float di ;
/* demonstrate 16-bit version */
for ( i = 4 ; i <= 8 ; i++ )
{
for ( j = 0 ; j <= 20 ; j++ )
(void)printf( " %d", rand16mod( i ) ) ;
printf( "\n" ) ;
}
/* time 16-bit version */
gettimeofday( &t1, (struct timezone *)NULL ) ;
for ( i = 0 ; i < ITERATIONS ; i++ )
;
gettimeofday( &t2, (struct timezone *)NULL ) ;
for ( i = 0 ; i < ITERATIONS ; i++ )
(void)rand16mod( 32 ) ;
gettimeofday( &t3, (struct timezone *)NULL ) ;
d1 = (t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec) ;
d2 = (t3.tv_sec - t2.tv_sec) * 1000000 + (t3.tv_usec - t2.tv_usec) ;
di = (d2 - d1) / (float) ITERATIONS ;
(void)printf( "microseconds 16-bit, null %d body %d iteration %f\n",
d1, d2, di ) ;
/* demonstrate 32-bit version */
for ( i = 4 ; i <= 8 ; i++ )
{
for ( j = 0 ; j <= 20 ; j++ )
(void)printf( " %d", rand32mod( i ) ) ;
printf( "\n" ) ;
}
/* time 32-bit version */
gettimeofday( &t1, (struct timezone *)NULL ) ;
for ( i = 0 ; i < ITERATIONS ; i++ )
;
gettimeofday( &t2, (struct timezone *)NULL ) ;
for ( i = 0 ; i < ITERATIONS ; i++ )
(void)rand32mod( 32 ) ;
gettimeofday( &t3, (struct timezone *)NULL ) ;
d1 = (t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec) ;
d2 = (t3.tv_sec - t2.tv_sec) * 1000000 + (t3.tv_usec - t2.tv_usec) ;
di = (d2 - d1) / (float) ITERATIONS ;
(void)printf( "microseconds 32-bit, null %d body %d iteration %f\n",
d1, d2, di ) ;
}
--
Lawrence Crowl 716-275-9499 University of Rochester
crowl@cs.rochester.edu Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl Rochester, New York, 14627wen-king@cit-vlsi.Caltech.Edu (Wen-King Su) (02/25/88)
In article <7097@sol.ARPA> crowl@cs.rochester.edu (Lawrence Crowl) writes: <#define NEGABS( i ) ((i) > 0 ? -(i) : (i)) >short rand16mod( modulus ) < short modulus ; > { < seed16 = (short)(seed16 * 25173) + 13849 ; > return (short)NEGABS(seed16) / (short)(-32768 / modulus) ; ^^^^^^^^^^^^^^^^^^^^^ Don't do this. Now you have a random number source that does not have an uniform distribution; both '0' and MAX_NEGATIVE occur at half the frequency as the other numbers. Use unsigned integers instead. Even if the random source is uniform over a range, say R, you can't expect the the result of a simple division to yield another uniform distribution unless R is a multiple of the divisor. For example, suppose the random source has a range of 0-7, and the divisor happens to be 3 (so that you get the numbers 0, 1, an 2 randomly). 0 / 3 -> 0 1 / 3 -> 0 2 / 3 -> 0 3 / 3 -> 1 4 / 3 -> 1 5 / 3 -> 1 6 / 3 -> 2 7 / 3 -> 2 <-- 2 only appear twice. In general, the correct way to do it is to use a random number generator of an appropriate range (the smallest power of 2 that is large enought to cover all the numbers you need). Then keep pulling numbers from the genenerator until you get the ones that falls in your range. unsigned my_random_source(); my_random(range) int range; { int value; do { value = my_random_source(); } while(value >= range); return(value); } /*------------------------------------------------------------------------*\ | Wen-King Su wen-king@vlsi.caltech.edu Caltech Corp of Cosmic Engineers | \*------------------------------------------------------------------------*/
crowl@cs.rochester.edu (Lawrence Crowl) (02/26/88)
In article <5555@cit-vax.Caltech.Edu> wen-king@cit-vlsi.UUCP (Wen-King Su) writes: >In article <7097@sol.ARPA> crowl@cs.rochester.edu (Lawrence Crowl) writes: ><#define NEGABS( i ) ((i) > 0 ? -(i) : (i)) >>short rand16mod( modulus ) >< short modulus ; >> { >< seed16 = (short)(seed16 * 25173) + 13849 ; >> return (short)NEGABS(seed16) / (short)(-32768 / modulus) ; > ^^^^^^^^^^^^^^^^^^^^^ >Don't do this. Now you have a random number source that does not have >an uniform distribution; both '0' and MAX_NEGATIVE occur at half the >frequency as the other numbers. Use unsigned integers instead. Since this was developed for a language providing only signed integers, the use of unsigned numbers did not occur to me. The asymmetry with reguards to 0 and MAX_NEGATIVE are lost in the noise since the codes purpose was speed, not extreme quality. The use of MAX_NEGATIVE provides the largest signed power of two. I have fixed this since it costs little. (Given the loss of inlining brought about by the loop introduced to fix the following problem.) >Even if the random source is uniform over a range, say R, you can't expect >the the result of a simple division to yield another uniform distribution >unless R is a multiple of the divisor. For example, suppose the random >source has a range of 0-7, and the divisor happens to be 3 (so that you get >the numbers 0, 1, and 2 randomly). If you look carefully at my old code, you will find that it uniformly generates numbers in the range 0 .. modulus-1. Unfortunately, it also occasionally generates the value modulus. This is not just a distribution problem, it is an outright bug. Taking Wen-King Su suggestions, I have redone the previous posting and provide the result here. Please throw out the old version and forget I ever posted it! The new code takes 60 micro-seconds for the 16-bit version and 150 micro-seconds for the 32-bit version on a Sun 2/170. /*-------------------------------------------------------------------- random.c This program contains a linear congruential pseudo-random number generator. Each random number generation takes a parameter, modulus, and returns a pseudo-random number in the range 0 ... modulus-1. The pseudo-random number is taken from the high-order bits of the seed. This file contains two versions of the generator, one for 16-bit arithmetic, and one for 32-bit arithmetic. Lawrence Crowl University of Rochester Computer Science Department Rochester, New York, 14627 */ /*-------------------------------------------------------------- 16-bit version This version assumes that shorts are 16 bits. This allows the code to run on machines with 32-bit ints but 16-bit hardware, such as the 68000. The extensive casting allows reasonable compilers to generate 16-bit multiply instructions. The coefficients for the generator are from Peter Grogono, "Programming in Pascal", Section 4.5, Addison-Wesley Publishing Company, 1978. I do not know if these coefficients have been tested. */ static unsigned short seed16 ; void rand16seed( seed ) unsigned short seed ; { seed16 = seed ; } short rand16mod( modulus ) register unsigned short modulus ; { register unsigned short result, reg_seed ; reg_seed = seed16 ; do { reg_seed = (unsigned short)(reg_seed * 25173) + 13849 ; result = (unsigned short)(reg_seed >> 1) / (unsigned short)(32767 / modulus) ; /* result = reg_seed / (unsigned short)(65535 / modulus) ; */ /* the Sun compiler thinks 65535 needs long division */ } while ( result >= modulus ) ; seed16 = reg_seed ; return result ; } /*-------------------------------------------------------------- 32-bit version This version assumes that ints are 32 bits. The coefficients for the generator are from David Dantowitz in article <11972@brl-adm.ARPA> of the comp.lang.c news group. I do not know if these coefficients have been tested. */ static unsigned int seed32 ; void rand32seed( seed ) unsigned int seed ; { seed32 = seed ; } int rand32mod( modulus ) register unsigned int modulus ; { register unsigned int result, reg_seed ; reg_seed = seed32 ; do { reg_seed = (reg_seed * 1103515245) + 12345 ; result = reg_seed / (4294967295 / modulus) ; } while ( result >= modulus ) ; seed32 = reg_seed ; return result ; } /*------------------------------------------------- demonstration program This is not a test program. For test procedures, see Donald E. Knuth, "The Art of Computer Programming", Chaper 3, Volume 2, Second Edition, Addison-Wesley Publishing Company, 1981 */ #include <stdio.h> #include <sys/time.h> #define ITERATIONS 100000 void main( argc, argv ) int argc ; char **argv ; { int i ; struct timeval t1, t2, t3 ; long d1, d2 ; float di ; int samples = atoi( argv[ 1 ] ) ; int modulus = atoi( argv[ 2 ] ) ; /* demonstrate 16-bit version */ for ( i = 0 ; i < samples ; i++ ) (void)printf( " %d", rand16mod( modulus ) ) ; printf( "\n" ) ; /* time 16-bit version */ gettimeofday( &t1, (struct timezone *)NULL ) ; for ( i = 0 ; i < ITERATIONS ; i++ ) ; gettimeofday( &t2, (struct timezone *)NULL ) ; for ( i = 0 ; i < ITERATIONS ; i++ ) (void)rand16mod( modulus ) ; gettimeofday( &t3, (struct timezone *)NULL ) ; d1 = (t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec) ; d2 = (t3.tv_sec - t2.tv_sec) * 1000000 + (t3.tv_usec - t2.tv_usec) ; di = (d2 - d1) / (float) ITERATIONS ; (void)printf( "microseconds 16-bit, null %d body %d iteration %f\n", d1, d2, di ) ; /* demonstrate 32-bit version */ for ( i = 0 ; i < samples ; i++ ) (void)printf( " %d", rand32mod( modulus ) ) ; printf( "\n" ) ; /* time 32-bit version */ gettimeofday( &t1, (struct timezone *)NULL ) ; for ( i = 0 ; i < ITERATIONS ; i++ ) ; gettimeofday( &t2, (struct timezone *)NULL ) ; for ( i = 0 ; i < ITERATIONS ; i++ ) (void)rand32mod( modulus ) ; gettimeofday( &t3, (struct timezone *)NULL ) ; d1 = (t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec) ; d2 = (t3.tv_sec - t2.tv_sec) * 1000000 + (t3.tv_usec - t2.tv_usec) ; di = (d2 - d1) / (float) ITERATIONS ; (void)printf( "microseconds 32-bit, null %d body %d iteration %f\n", d1, d2, di ) ; } -- Lawrence Crowl 716-275-9499 University of Rochester crowl@cs.rochester.edu Computer Science Department ...!{allegra,decvax,rutgers}!rochester!crowl Rochester, New York, 14627
m5@bobkat.UUCP (Mike McNally ) (02/26/88)
Linear congruential random number generators are fine because of their
simplicity, but unless the entire seed is used the results are not very
random. Get ahold of a graphics system and do a simple pairs test by
plotting random x-y positions for a while. You'll see nifty patterns.
The BSD (?) random() functions are decidedly superior, though somewhat
slower.
--
Mike McNally, mercifully employed at Digital Lynx ---
Where Plano Road the Mighty Flood of Forest Lane doth meet,
And Garland fair, whose perfumed air flows soft about my feet...
uucp: {texsun,killer,infotel}!pollux!bobkat!m5 (214) 238-7474mcdonald@uxe.cso.uiuc.edu (02/26/88)
Has anyone out there considered how to write a random number generator in
which the output is truly random? In my tests it seems that the low-order
bits have a very short repetition period. I've considered using two
ordinary generators giving 32-bit periods and patching together the high
order words. Is this better?
When I really needed a REAL random number, what I actually did was
to read the output of a analog-to-digital converter connected to a noise
source and XOR that with my ordinary generator. This only works if your
computer has an adc, unfortunately.
Doug McDonaldfranka@mmintl.UUCP (Frank Adams) (02/27/88)
In article <5555@cit-vax.Caltech.Edu> wen-king@cit-vlsi.UUCP (Wen-King Su) writes: >In general, the correct way to do it is to use a random number generator >of an appropriate range (the smallest power of 2 that is large enough to >cover all the numbers you need). Then[:] > >unsigned my_random_source(); > >my_random(range) > int range; >{ > int value; > do { value = my_random_source(); } while(value >= range); > return(value); >} This is fine if 'range' is a reasonably large number. On the other hand, if it is 2, it works very badly. More generally, try: unsigned my_random_source(); int source_limit; my_random(range) int range; { int value; int multiplicity = source_limit / range; int limit = multiplicity * range do { value = my_random_source(); } while(value >= limit); return(value / multiplicity); } To be on the safe side, you could add a check for limit != 0. There are techniques for dealing with that case, but it is usually best to just increase the size of the numbers you are getting from the generator. -- Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Ashton-Tate 52 Oakland Ave North E. Hartford, CT 06108
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/28/88)
In article <225800009@uxe.cso.uiuc.edu> mcdonald@uxe.cso.uiuc.edu writes: >Has anyone out there considered how to write a random number generator in >which the output is truly random? Yes, you need a truly random mechanism, such as a radiation counter or resistive thermal noise (as you say you once did). Deterministic algorithms will of course always have intrinsic regularities. >In my tests it seems that the low-order bits have a very short repetition >period. I've considered using two ordinary generators giving 32-bit periods >and patching together the high order words. Is this better? It depends on how you're using the pseudo-random sequence. I suggest you read Chapter 3 of Donald Knuth's "The Art of Computer Programming" (in Volume 2, "Seminumerical Algorithms", 2nd ed., Addison-Wesley 1981, ISBN 0-201-03822-6).
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/28/88)
In article <3472@bobkat.UUCP> m5@bobkat.UUCP (Mike McNally (Man from Mars)) writes: >Linear congruential random number generators are fine because of their >simplicity, but unless the entire seed is used the results are not very >random. Get ahold of a graphics system and do a simple pairs test by >plotting random x-y positions for a while. You'll see nifty patterns. There are patterns in the sequences produced by any deterministic generator, although you may not be able to see them via simple plotting. This is what makes cryptanalysis of machine ciphers feasible. >The BSD (?) random() functions are decidedly superior, though somewhat >slower. Those use a linear-feedback shift-register method (if used in a mode where the state information is greater than 32 bits). Golomb wrote a whole book about the algebra and statistics of such sequences. LFSR sequences can act as if they are "more random" than LC sequences for naive use, but it does depend on what you use them for. UNIX System V provides 48-bit LC sequence generators under names such as irand48(), drand48(), etc. Because these use more bits than the example code I posted, they are generally better. It is too bad that there doesn't seem to be a single, FAST, statistically dominant method that could be provided for all applications. Programmers keep having to provide their own RNGs to have sufficient confidence in their suitability for specific applications.
cik@l.cc.purdue.edu (Herman Rubin) (02/28/88)
(This doesn't belong in comp.lang.c, but too much has already been posted). I would never use a pseudo-random procedure for any job of any importance. However, let me make some suggestions about good, cheap procedures. First, do not make a subroutine call for each random number wanted. Use a buffer! Second, get some physical random bits. And make sure that all bits are random. Third, probably you should want your initial random numbers to be words of random bits. Keep away from floating point or positive random numbers. A fairly good combination of physical and pseudo-random numbers is to have a pseudo-random procedure which uses a long word-shift-register algorithm such as x[i] = x[i-460] XOR x[i-607]; One could replace XOR by + if addition is full-word two's complement. Then one should make the used random variables y[i] = x[i] XOR z[i], where the z's are physical random numbers. For a large job, the z's have to be recycled. The length of the physical random number file should not be too close to a rational number with small numerator and denominator times a power of 2. Even using the pseudo-random numbers alone with a 607-word physical random seed is likely to be much better than anyting else posted here. A major reason for using physical random numbers is that a pseudo-random scheme is likely to have unknown regularities, which the physical random numbers are unlikely to match; a good reason to include the pseudo-random numbers is to guarantee uniformity; one cannot trust the physical random numbers that much. With a good seed, the procedures suggested by Shamir and by Blum and Miccaeli might even be better, but they are very expensive. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet
ok@quintus.UUCP (Richard A. O'Keefe) (02/29/88)
In article <690@l.cc.purdue.edu>, cik@l.cc.purdue.edu (Herman Rubin) writes: > Second, get some physical random bits. > And make sure that all bits are random. Um, how *do* you "make sure that all bits are random"? Physical random numbers aren't all that simple, either. Radioactives decay, noise diodes die, electrochemical methods have hazards of their own, the noise spectrum of the source depends on the ambient temperature, and so on. In effect, you have to re-validate a physical source each time you use it. Journals like JASA and Applied Statistics seem to be happy with the use of pseudo-random numbers in Monte Carlo studies.
cik@l.cc.purdue.edu (Herman Rubin) (03/01/88)
In article <709@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) writes: > In article <690@l.cc.purdue.edu>, cik@l.cc.purdue.edu (Herman Rubin) writes: > > Second, get some physical random bits. > > And make sure that all bits are random. > Um, how *do* you "make sure that all bits are random"? > Physical random numbers aren't all that simple, either. I meant that the physical random number should be on a storage device. I did point out that they might have to be reused. > Journals like JASA and Applied Statistics seem to be happy with the > use of pseudo-random numbers in Monte Carlo studies. I would not trust them. They may take this attitude because they do not know that there is a cheap alternative. About 15 years ago, one of my colleagues came to me about a simulation problem--his 5% significance values (known theoretically) were coming out 7%. Changing the random numbers to XOR with the a binary version of the RAND numbers solved the problem. Many Monte Carlo studies suffer from this and other defects. One should always put in checks with directly calculable quantities--are you that sure that you have not made a programming error? There are several sets of physical random numbers available. Also note that I recommended that physical and pseudo random numbers be XORed; we only need assume that the physical random numbers do not have their quirks matching the quirks of the pseudo random numbers. That is a much smaller assumption than saying the pseudo random numbers' quirks will not affect the simulation. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet
Rik.Stevans@f226.n105.z1.FIDONET.ORG (Rik Stevans) (08/20/89)
Does anyone have a good random number generator for 'c'? i need a
function which will return an integer less than zero (just like rnd
in basic) and be fairly random. the one i wrote does ok but is very
unweildly as i cast from double back to int to get the numbers i need.
thanks, rik s...
--
Rik Stevans - via FidoNet node 1:105/14
UUCP: ...!{uunet!oresoft, tektronix!reed}!busker!226!Rik.Stevans
ARPA: Rik.Stevans@f226.n105.z1.FIDONET.ORGping@cubmol.BIO.COLUMBIA.EDU (Shiping Zhang) (08/21/89)
In article <876.24EFA953@busker.FIDONET.ORG> Rik.Stevans@f226.n105.z1.FIDONET.ORG (Rik Stevans) writes: >Does anyone have a good random number generator for 'c'? i need a >function which will return an integer less than zero (just like rnd >in basic) and be fairly random. the one i wrote does ok but is very >unweildly as i cast from double back to int to get the numbers i need. >thanks, rik s... >-- >Rik Stevans - via FidoNet node 1:105/14 > UUCP: ...!{uunet!oresoft, tektronix!reed}!busker!226!Rik.Stevans > ARPA: Rik.Stevans@f226.n105.z1.FIDONET.ORG There are functions that generate random integers in the C standard library. Take a look at your manual. -ping
mburkey@gara.une.oz (Marty) (08/22/89)
In article <876.24EFA953@busker.FIDONET.ORG>, Rik.Stevans@f226.n105.z1.FIDONET.ORG (Rik Stevans) writes: > Does anyone have a good random number generator for 'c'? i need a > function which will return an integer less than zero (just like rnd There are two random functions that have been written for C. (Though I haven't the faintest wot compilers have got 'em and wot haven't). rand() and random() come with associated srand() and srandom() functions to start the sewuence at a given point rather tha at the beginning. If they happen to be in your libraries then they will most likely happen to be in math.h - but if they ain't there then they ain't anywhere. Failing that, just about any Comp. Svi. text book will have a random number generation algorithm. -Marty.
meissner@dg-rtp.dg.com (Michael Meissner) (08/22/89)
In article <324@cubmol.BIO.COLUMBIA.EDU> ping@cubmol.UUCP (Shiping Zhang) writes: | In article <876.24EFA953@busker.FIDONET.ORG> Rik.Stevans@f226.n105.z1.FIDONET.ORG (Rik Stevans) writes: | >Does anyone have a good random number generator for 'c'? i need a | >function which will return an integer less than zero (just like rnd | >in basic) and be fairly random. the one i wrote does ok but is very | >unweildly as i cast from double back to int to get the numbers i need. | >thanks, rik s... | >-- | >Rik Stevans - via FidoNet node 1:105/14 | > UUCP: ...!{uunet!oresoft, tektronix!reed}!busker!226!Rik.Stevans | > ARPA: Rik.Stevans@f226.n105.z1.FIDONET.ORG | | There are functions that generate random integers in the C standard | library. Take a look at your manual. But the requestor wanted a "GOOD" random number generator, and "rand" which is in the C standard, is typically not all that good. If your system is based on Berkeley, look up "random(3)" in the documentation. If your system is based on System V, look up "lrand48(3)" and friends. These random number generators are much better. Typical seed values in UNIX are based on the time of day, date and/or process ID. -- Michael Meissner, Data General. Uucp: ...!mcnc!rti!xyzzy!meissner If compiles were much Internet: meissner@dg-rtp.DG.COM faster, when would we
flaps@dgp.toronto.edu (Alan J Rosenthal) (08/23/89)
mburkey@gara.une.oz (Marty) writes: > There are two random functions that have been written for C. ... [ rand() and random() ] > If they happen to be in your libraries then they will most likely happen to > be in math.h - but if they ain't there then they ain't anywhere. Hormph! math.h is for floating-point routines only, despite its name. I've never seen one contain a rand() or random() declaration, and I never hope to see one. (But I can tell you anyhow, I'd rather see than be one! %) (However, in the version of QNX we have at my other job, math.h declares atol() and ftell()! The authors apparently thought that math.h should declare all functions whose declarations were absolutely necessary in that they returned non-two-byte types. Disgusting. (stdio.h doesn't declare ftell() on that system.)) ajr % probably copyright, as it is half of the work in question. Three-quarters, actually, including the last bit of the previous sentence.
andrew@alice.UUCP (Andrew Hume) (08/30/89)
if you can tolerate a congruential style generator, try this:
/*
random number generator from cacm 31 10, oct 88
for 32 bit integers (called long here)
*/
#ifdef MAIN
#define A 16807 /* good numbers */
#define M 2147483647
#define Q 127773
#define R 2836
#else
#define A 48271 /* better numbers */
#define M 2147483647
#define Q 44488
#define R 3399
#endif
static long seed;
srand(unsigned newseed)
{
seed = newseed;
}
rand()
{
long lo, hi, test;
hi = seed/Q;
lo = seed%Q;
test = A*lo - R*hi;
if(test > 0)
seed = test;
else
seed = test+M;
return(seed);
}
#ifdef MAIN
main()
{
int i;
srand(1);
for(i = 0; i < 10000; i++)
rand();
if(seed == 1043618065)
printf("implementation looks correct\n");
else
printf("uh oh! seed=%u, should be 1043618065\n", seed);
exit(0);
}
#endif
compile with -DMAIN to test.penneyj@servio.UUCP (D. Jason Penney) (09/01/89)
In article <9849@alice.UUCP> andrew@alice.UUCP (Andrew Hume) writes: > > >if you can tolerate a congruential style generator, try this: > If you can NOT tolerate a congruential style generator, try this: (sorry, no test program or main -- shouldn't be a problem, though...) /*======================================================================== * * Name - %M% - random.hf * * Version: %I% * * ccsid: %W% - %G% %U% * from: %F% * date: %H% %T% * * %Q% * * Description: * *========================================================================*/ void RandomInit(void); unsigned int Random(void); unsigned int RandomBetween__and__(unsigned int lower, unsigned int upper); /*======================================================================== * * Name - %M% -- random.c * * Version: %I% * * ccsid: %W% - %G% %U% * from: %F% * date: %H% %T% * * %Q% * * Description: Random Number Generator * *========================================================================*/ #include <random.hf> #include <time.h> /* This size must be power of two because of strange arithmetic we must go through: */ #define auxRandomTableSize 64 static unsigned int auxRandomTable[auxRandomTableSize]; static unsigned int randomSeed, /* for repeated operation */ knuth_shuffler /* for Algorithm D */; static unsigned int nextCyclicRandom(void) /* Note: according to Knuth volume 2, this generator has some serious flaws, depending on how it is used. We incorporate this generator with another randomization scheme to produce FUNCTION RANDOM. */ { /* Note we take advantage of C arithmetic not to signal arithmetic overflow. */ randomSeed = (unsigned int)((13849L + 27181L * randomSeed) & 65535L); return randomSeed; } void RandomInit(void) /* random number initialization */ { int i; randomSeed = (unsigned int)(clock()); for (i = 0; i < auxRandomTableSize; i ++) auxRandomTable[i] = nextCyclicRandom(); knuth_shuffler = nextCyclicRandom(); } /* Random Number Generation */ unsigned int Random(void) /* See Knuth volume 2, page 32, "Algorithm B" */ { int j; /* B1 */ j = (int)(knuth_shuffler * auxRandomTableSize / 65536); /* B2 */ knuth_shuffler = auxRandomTable[j]; auxRandomTable[j] = nextCyclicRandom(); return knuth_shuffler; } unsigned int RandomBetween__and__(unsigned int lower, unsigned int upper) { unsigned int modulus, threshold, probe; if ((upper == 65535) && (lower == 0)) /* easy */ return Random(); modulus = upper - lower + 1; threshold = (int)(65535 / modulus * modulus); do { probe = Random(); } while (probe >= threshold); /* to make perfectly uniform */ return lower + probe % modulus; } -- D. Jason Penney Ph: (503) 629-8383 Beaverton, OR 97006 uucp: ...uunet!servio!penneyj STANDARD DISCLAIMER: Should I or my opinions be caught or killed, the company will disavow any knowledge of my actions...
jonas@lkbpyr.UUCP (Jonas Heyman) (01/01/90)
Hello,
I want this program below to generate 10 different randomly numbers,
but it seems to generate the same ten when you execute the c program.
How do I solve this ?
-----------------------------
main()
{
int number=0;
int i=0;
while (i<10) {
i++;
number=rnd();
printf("%d\n",number);
}
}
rnd()
{
int i=0;
int long now;
srand(time(&now)%37);
return(rand());
}
------------------------------------
Sincerely Jonas
--
jonas@lkbpyr.lkb.se ping@cubmol.bio.columbia.edu (Shiping Zhang) (01/03/90)
In article <397@lkbpyr.UUCP> jonas@lkbpyr.UUCP (Jonas Heyman) writes: >Hello, > >I want this program below to generate 10 different randomly numbers, >but it seems to generate the same ten when you execute the c program. > >How do I solve this ? > while (i<10) { > i++; > number=rnd(); > printf("%d\n",number); > } >rnd() >{ > int i=0; > int long now; > > srand(time(&now)%37); > return(rand()); >} This is because the computer works much much faster than people think it would. From the begin to the end of the while loop, the time spent is not long enough for time() to return a different number. So srand will have the same seed, which results in rand() returning the same first number of a list of random numbers. It's very simple to solve this problem, that is to call srand() only once before the while loop in the main() domain, then just only call rand() subseqently to get 'random' numbers. -ping