Random number generator in gcc
Chia Hsun Gwen Wang
"like srand and rand" except that drand48's output is [0,1)... This may
turn out not to be a C issue, but it's arguable.]
Hi everyone,
I need help on generating random number in unix gcc.
I am currently using Srand48(time(NULL)) to initialize the
seed, and then use dran48() to generate random number between (0,1).
The problem is that when I call this routine in a for loop, it generates out
the same random numbers. But, if I do it in a slower manner ( like input some
data, then generate the random number), then the routine works fine. Anyone
have any suggestions?
Thanks!
S. Lee
Chia Hsun Gwen Wang <ch...@caelab1.cae.wisc.edu> wrote:
> I need help on generating random number in unix gcc.
> I am currently using Srand48(time(NULL)) to initialize the
>seed, and then use dran48() to generate random number between (0,1).
>The problem is that when I call this routine in a for loop, it generates out
>the same random numbers. But, if I do it in a slower manner ( like input some
>data, then generate the random number), then the routine works fine. Anyone
>have any suggestions?
You are probably seeding the generator more than once, in the same second
so they get the same seed (thus the same value when you call drand48()).
Call Srand48 only ONCE at the beginning of your program.
sl...@cornell.edu
Witty .sig under construction.
Karsten Spang
[well, I'll leave it alone for the moment. However, people responding mostly
to the gcc aspects of the discussion should keep that in mind when following
up. -mod]
In article <3k8btj$6...@blackice.winternet.com>, ch...@caelab1.cae.wisc.edu (Chia Hsun Gwen Wang) writes:
|> I am currently using Srand48(time(NULL)) to initialize the
|> seed, and then use dran48() to generate random number between (0,1).
|> The problem is that when I call this routine in a for loop, it generates out
|> the same random numbers. But, if I do it in a slower manner ( like input some
|> data, then generate the random number), then the routine works fine. Anyone
|> have any suggestions?
To me, it looks like gcc has optimised the call out of the loop. Did you try
to compile without optimisation? Has drand48() (mistakenly) been declared
with "__attribute__ ((const))" in some header file?
Karsten
--
Karsten Spang Snail Mail: Kampsax Data
E-mail: k...@kampsax.dk +-------------------------------+ P.O. Box 1142
Phone: +45 36 39 07 88 | Warning: No keyboard detected | DK-2650 Hvidovre
Fax: +45 36 77 03 01 | Press <RETURN> to continue | Denmark
--------------------------------------------------------------------------------
Dan Pop
>[seebs: Although srand48/drand48 are not standard C, their behavior is
> "like srand and rand" except that drand48's output is [0,1)... This may
> turn out not to be a C issue, but it's arguable.]
Apparently, it is connected with the way time() works in Unix.
>
>Hi everyone,
>
> I need help on generating random number in unix gcc.
> I am currently using Srand48(time(NULL)) to initialize the
>seed, and then use dran48() to generate random number between (0,1).
>The problem is that when I call this routine in a for loop, it generates out
>the same random numbers. But, if I do it in a slower manner ( like input some
>data, then generate the random number), then the routine works fine. Anyone
>have any suggestions?
>
If you do this in a very tight loop, chances are that you call srand()
many times within the same second, and the value returned by time() has
a one second granularity.
The situation can be somewhat improved by using
srand((unsigned)clock() + (unsigned)time(NULL));
clock() has a finer granularity than time() and the sum of the two values
gives different seeds on different runs of the program.
The casts to unsigned are needed to avoid signed integer arithmetic
overflow.
The solution is safe in Unix, where both clock() and time() are known to
return integer values, but it cannot be used in code which has to be
portable to other systems.
Dan
--
Dan Pop
CERN, CN Division
Email: dan...@cernapo.cern.ch
Mail: CERN - PPE, Bat. 31 R-004, CH-1211 Geneve 23, Switzerland
Dan Stubbs
Chia Hsun Gwen Wang <ch...@caelab1.cae.wisc.edu> wrote:
The following has the advantage that its characteristics are discussed
in the reference, and there is a test to make sure it works correctly
in the environment it which it is to be used. A number of other
random number generators are also discussed.
Dan Stubbs
dst...@galaxy.calpoly.edu
/*--------------------------------------------------------------------*/
/*----- Park, S.K., and Miller, K.W., "Random Number Generators: -----*/
/*----- Good Ones Are Hard to Find," Communications of the ACM, -----*/
/*----- Oct., 1988, pp 1192-1201. -----*/
/*--------------------------------------------------------------------*/
int random (int old) {
/*--------------------------------------------------------------------*/
/*----- There is a simple test to verify that the implementation -----*/
/*----- is correct. See below. -----*/
/*--------------------------------------------------------------------*/
static int a = 16807, m = 2147483647, q = 127773, r = 2836;
int new;
new = a*(old % q) - r*(old / q);
if (new > 0) return new;
else return (new + m);
}
/*--------------------------------------------------------------------*/
/*----- Test to verify the implementation -----*/
/*--------------------------------------------------------------------*/
/*
int main () {
int k, num;
printf("Random Number Test\n");
num = 1;
for (k=1; k <= 10005; k++) {
num = Rand(num);
if (k > 9995) {
put_commas(k, 8); <-- Use printf instead of this
put_commas(num, 15); <-- local function.
putchar('\n');
}
}
}
Random Number Test
k random number
-------+---------------
9,996 721,631,166 <-- printf will work, but put_commas
9,997 1,614,852,353 <-- makes much nicer results.
9,998 925,166,085
9,999 1,484,786,315
10,000 1,043,618,065 <-- Test is to get this value!!!!!
10,001 1,589,873,406
10,002 2,010,798,668
10,003 543,060,237
10,004 407,903,509
10,005 866,474,539
*/
/*--------------------------------------------------------------------*/
Greg Wooledge
> I am currently using Srand48(time(NULL)) to initialize the
>seed, and then use dran48() to generate random number between (0,1).
>The problem is that when I call this routine in a for loop, it generates out
>the same random numbers.
Dan Pop pointed out (correctly) that a time_t cannot be guaranteed to be
convertible into an unsigned integral type. But for most architectures
your use of time() to seed the random number generator is acceptable.
Having warned you about possible problems here, I will henceforth
concentrate only on "real" issues. :-)
Two ideas spring to mind:
(1) You may be calling srand48() inside the loop, thereby reseeding
your generator. Since the output of time() may change very slowly,
this may seed the generator with the same value many times in a row.
(2) You may have some subtle problem with your code which causes the
behavior you observed. Without sample code to analyze, this seems
quite possible, even likely. Possibilities include the use of '1'
instead of 'i' as an array index; the use of uninitialized pointers,
or pointers which all point to the same place; etc.
Try the following program, which works as expected under AIX:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main (int argc, char *argv[])
{
int i;
if (argc < 2)
{
if (argc == 1)
{
printf ("usage: %s iterations\n", argv[0]);
}
return EXIT_FAILURE;
}
srand48 (time (NULL));
for (i = atoi (argv[1]); i > 0; i--)
{
printf ("%f\n", drand48());
}
return EXIT_SUCCESS;
}
P.S. -- I use srand (time (0)) for my programs. :-)
--
# Greg Wooledge /..\
# bh...@summitis.com \--/ Have a day.
# aa1...@freenet.lorain.oberlin.edu (good luck)
Michael Staats
rexago8!bh...@uunet.uu.net (Greg Wooledge) writes:
>P.S. -- I use srand (time (0)) for my programs. :-)
Yes, I also use time() to initialize a random number generator. But
for all real life problems I recommend to store the seed in a variable
and save it in a file. This makes your data reproducable, this is
quite important if you find some strange situation in a random system
and want to reproduce the results.
Bye,
Michael
--
Michael Staats, Theoretical Physics, Uni-GH Duisburg
email: mic...@hal6000.thp.Uni-Duisburg.DE
<a href="http://WWW.thp.Uni-Duisburg.DE/">Click</a> me!
<a href="http://WWW.thp.Uni-Duisburg.DE/cuaix/cuaix.html">A c.u.aix archive</a>
David Kastrup
>In <3k8btj$6...@blackice.winternet.com> ch...@caelab1.cae.wisc.edu (Chia Hsun Gwen Wang) writes:
>>[seebs: Although srand48/drand48 are not standard C, their behavior is
>> "like srand and rand" except that drand48's output is [0,1)... This may
>> turn out not to be a C issue, but it's arguable.]
>Apparently, it is connected with the way time() works in Unix.
>>
>>Hi everyone,
>>
>> I need help on generating random number in unix gcc.
>> I am currently using Srand48(time(NULL)) to initialize the
>>seed, and then use dran48() to generate random number between (0,1).
>>The problem is that when I call this routine in a for loop, it generates out
>>the same random numbers. But, if I do it in a slower manner ( like input some
>>data, then generate the random number), then the routine works fine. Anyone
>>have any suggestions?
>>
>If you do this in a very tight loop, chances are that you call srand()
>many times within the same second, and the value returned by time() has
>a one second granularity.
>The situation can be somewhat improved by using
>srand((unsigned)clock() + (unsigned)time(NULL));
>clock() has a finer granularity than time() and the sum of the two values
>gives different seeds on different runs of the program.
No, no, no, no NOOOOOO! rand is *not* designed to cryptographically
strong hash a system time value or whatever, and produce reasonable
sequences. It produces reasonable sequences once you have
initialized it. You *must* initialize it only *once* using srand,
then the sequence generated from rand will have good pseudorandom
properties up to the next call of srand (at least, in theory). But
those properties are not at all guaranteed if you keep initializing
your random generator.
Put that srand out of the loop!
--
David Kastrup, Goethestr. 20, D-52064 Aachen Tel: +49-241-72419
Email: d...@pool.informatik.rwth-aachen.de Fax: +49-241-79502
Thomas Richard Dibble
David> dan...@cernapo.cern.ch (Dan Pop) writes:
>> In <3k8btj$6...@blackice.winternet.com> ch...@caelab1.cae.wisc.edu (Chia
>> Hsun Gwen Wang) writes:
>>> [seebs: Although srand48/drand48 are not standard C, their behavior is
>>> "like srand and rand" except that drand48's output is [0,1)... This
>>> may turn out not to be a C issue, but it's arguable.]
>>> Hi everyone,
>>>
>>> I need help on generating random number in unix gcc. I am currently
>>> using Srand48(time(NULL)) to initialize the seed, and then use
>>> dran48() to generate random number between (0,1). The problem is that
>>> when I call this routine in a for loop, it generates out the same
>>> random numbers. But, if I do it in a slower manner ( like input some
>>> data, then generate the random number), then the routine works
>>> fine. Anyone have any suggestions?
>>>
[ ... ]
David> No, no, no, no NOOOOOO! rand is *not* designed to cryptographically
David> strong hash a system time value or whatever, and produce reasonable
David> sequences. It produces reasonable sequences once you have
David> initialized it. You *must* initialize it only *once* using srand,
David> then the sequence generated from rand will have good pseudorandom
David> properties up to the next call of srand (at least, in theory). But
David> those properties are not at all guaranteed if you keep initializing
David> your random generator.
Exactly. However, for better results, you can re-seed after user input
(assuming that user input is actually from the user and not a key-faking
TSR or pipe or somesuch). If your program seeds at the start, then
re-seeds after executing a few instructions which will always take the same
amount of time to execute (like in the described loop above) you gain
nothing and lose the time used to reseed your generator. If you reseed
after variable-length instructions (getting input from a user and a long
sequence of instructions, or *long* sequences of instructions in a
preemptive multitasking environment) you may increase the pseudo-random
nature of your series by factoring in user response times as well as the
program start-up time.
But this is just a rather minimal-use thing. As a general rule, the random
number generator should be seeded exactly once, at the program start.
---- Tom Dibble
--
/"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""\
| Tired of lying in the sunshine, \ / tom...@wpi.wpi.edu |
| staying home to watch the rain. / \ the happiest man alive |
\.........................................................................../
Dan Pop
>No, no, no, no NOOOOOO! rand is *not* designed to cryptographically
>strong hash a system time value or whatever, and produce reasonable
>sequences. It produces reasonable sequences once you have
>initialized it. You *must* initialize it only *once* using srand,
>then the sequence generated from rand will have good pseudorandom
>properties up to the next call of srand (at least, in theory). But
>those properties are not at all guaranteed if you keep initializing
>your random generator.
>
>Put that srand out of the loop!
This is not necessarily true. Breaking the pseudorandom sequence might
be necessary, in certain cases. If you run a number of separate
simulations within the main loop, you have no way to store the seed of
a certain simulation, just in case you want to reproduce it later, with
a modified version of the code and compare the results. The only
solution is to reseed the random generator and save the seed together
with the results of the simulation.
If you run this code on a Pentium box, this is quite a good idea.
You don't change the code, you change the cpu and rerun the simulation
which produced dubious results :-)
Michael Staats
>But this is just a rather minimal-use thing. As a general rule, the random
>number generator should be seeded exactly once, at the program start.
Ok, sorry for the nitpicking, but this is USENET :-)
I already mentioned that it is important to save the seed to be abel
to reproduce the results you get.
I have programs where I initialize the random generator --
(BTW: rand() is usually quite bad, drand48() is good but slow, so
you'd better take the one from D. Knuth, The art of computer
programming, Vol. 2, or from Kirkpatrick and Scholl, Journal of
Computational Physics 40, 517-526, 1981.)
-- ok, I have programs where I initialize the random generator twice: The
first time with a seed that is read from a configuration file, this is
done to make sure that some initial conditions are the same for many
runs, the second time where some simulation starts, this time I
initialize from time() and save the seed in the output file.
Morten J|hnk
>Hi everyone,
>Thanks!
Is the Srand(time(NULL)) inside the loop as well ? If it is, you'll
initialize the seed with the same timestamp many times - if the loop
is fast enough. You should only call srand once.
Morten Joehnk
--
Herman Rubin
>>Thanks!
There is no good, or even fair, reason to have a random number generator
as part of the C language, or a "standard" C system. All of them can be
added on, and without much difficulty. In addition, none of them is random;
they are what are called pseudo-random, and whether these do the job
expected is always problematical. There are some "cryptographically strong"
generators, but they are very slow and involve high precision integer
arithmetic.
I suggest that one goes to a buffer system, and use some such generator
as x[n] = x[n-k] XOR x[n-j]; using addition is somewhat better. This
is integer arithmetic, with carries ignored if addition is used. There
are tables of good pairs. Even better would be to XOR these with
physically generated numbers, which may have to be recycled.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hru...@stat.purdue.edu (Internet, bitnet)
{purdue,pur-ee}!a.stat!hrubin(UUCP)
Rick Busdiecker
There is no good, or even fair, reason to have a random number generator
as part of the C language, or a "standard" C system. All of them can be
added on, and without much difficulty. In addition, none of them is random;
they are what are called pseudo-random, and whether these do the job
expected is always problematical. There are some "cryptographically strong"
generators, but they are very slow and involve high precision integer
arithmetic.
I agree with the sentiment expressed in the article. However, I'd like to
nitpick just a bit. It is believed to be possible to write code in C/Unix
which generates random numbers. The enclosed program was posted to the
Cypherpunks mailing list by Matt Blaze <m...@research.att.com>, the guy who
found the LEAF bug in the Clipper chip on January 20th of this year.
It's extremely slow -- one random bit per second -- because it's not designed
to be fast, but rather to have it's result be truly random, that is to have
it's result derived from a fundamentally random physical process.
This is believed to generate truly random bits on virtually any current unix
system.
- - - - - - - - - - - - - - - - - Clip Here - - - - - - - - - - - - - - - - -
#include <stdio.h>
#include <signal.h>
int count=0;
void printbit()
{
signal(SIGALRM,printbit);
alarm(1);
printf("%1d",count&01);
fflush(stdout);
}
main()
{
signal(SIGALRM,printbit);
alarm(1);
while (1)
count++;
}
- - - - - - - - - - - - - - - - - Clip Here - - - - - - - - - - - - - - - - -
--
Rick Busdiecker <r...@lehman.com> Please do not send electronic junk mail!
Lehman Brothers Inc.
3 World Financial Center "The more laws and order are made prominent, the
New York, NY 10285-1100 more thieves and robbers there will be." --Lao Tzu
Ronald F. Guilmette
Rick Busdiecker <r...@lehman.com> wrote:
>... The enclosed program was posted to the
>Cypherpunks mailing list by Matt Blaze <m...@research.att.com>, the guy who
>found the LEAF bug in the Clipper chip on January 20th of this year.
>
>It's extremely slow -- one random bit per second -- because it's not designed
>to be fast, but rather to have it's result be truly random, that is to have
>it's result derived from a fundamentally random physical process.
Are there any such things as ``fundamentally random physical processes''?
(Perhaps follow-ups should be directed to alt.philosophy.determinism.)
--
-- Ron Guilmette, Sunnyvale, CA ---------- RG Consulting -------------------
---- E-mail: r...@segfault.us.com ----------- Purveyors of Compiler Test ----
-------------------------------------------- Suites and Bullet-Proof Shoes -
Lawrence Kirby
r...@lehman.com "Rick Busdiecker" writes:
> It's extremely slow -- one random bit per second -- because it's not designed
> to be fast, but rather to have it's result be truly random, that is to have
> it's result derived from a fundamentally random physical process.
The process appears to be fundamentally non-random.
> This is believed to generate truly random bits on virtually any current unix
> system.
It produces results due to actions (swapping, interrupts, cache
activity etc.) in the rest of the system) that are difficult to predict but
this doesn't equate to 'truely random'. Fundamentally random physical
processes are things like nuclear decay. This is based on the relative timing
of 2 events which, typically, are derived on the same clock source. There
could well be circumstances which generare a precice number of clock ticks
between alarm events.
>
> - - - - - - - - - - - - - - - - - Clip Here - - - - - - - - - - - - - - - - -
> #include <stdio.h>
> #include <signal.h>
> int count=0;
volatile sig_atomic_t count=0;
would be better since (and required by ANSI to make the program defined). OK,
the code is probably designed to work with pre-ANSI compilers but a compiler
could easily move the count variable in the while loop to a register. ANSI
has been around long enough now for people to use it in examples.
> void printbit()
> {
> signal(SIGALRM,printbit);
> alarm(1);
> printf("%1d",count&01);
> fflush(stdout);
> }
> main()
> {
> signal(SIGALRM,printbit);
> alarm(1);
> while (1)
> count++;
count ^= 1;
would be better since it avoids the possibility of signed integer overflows
and the undefined behaviour that results.
> }
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Rick Busdiecker
> This is believed to generate truly random bits on virtually any
> current unix system.
It produces results due to actions (swapping, interrupts, cache
activity etc.) in the rest of the system) that are difficult to predict but
this doesn't equate to 'truely random'.
The situation is more serious than merely ``difficult to predict''.
It is not possible to measure the physical processes involved, with
the precision necessary to make a prediction, without disturbing those
processes enough to change the outcome. You could build a machine for
which this was not the case, it just hasn't been done yet.