Final fix for correlation problem (was Re: rand() is broken)
This is final fix for 1st value correlation problem. Somebody with
math statistic knowledge please run some test to be sure that NSHUFF is
good enough for this simple PRNG (i.e. not 100% good, but good for average
quality PRNG we have). My simple test shown that 100 is enough, but I
am not PRNG math expert. Maybe increasing NSHUFF up too 2000 required.
Similar patch is needed for random(3) TYPE_0 too, I'll produce it when we
find good NSHUFF.
--- stdlib/rand.c.bak Mon Feb 3 13:22:12 2003
+++ stdlib/rand.c Mon Feb 3 14:03:58 2003
@@ -51,6 +51,8 @@
#include stdio.h
#endif /* TEST */
+#define NSHUFF 100 /* to drop seed - 1st value correlation */
+
static int
do_rand(unsigned long *ctx)
{
@@ -108,7 +110,11 @@
srand(seed)
u_int seed;
{
+ int i;
+
next = seed;
+ for (i = 0; i NSHUFF; i++)
+ (void)do_rand(next);
}
@@ -137,7 +143,7 @@
unsigned long junk;
gettimeofday(tv, NULL);
- next = (getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk;
+ srand((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
}
}
--
Andrey A. Chernov
http://ache.pp.ru/
msg51666/pgp0.pgp
Description: PGP signature
Re: Final fix for correlation problem (was Re: rand() is broken)
I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? I have worked with programs that depend on exactly that behavior. That is, given the same input seed - I expect to see the same random sequence again. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... Please, oh please, don't change that behavior in srand()/rand(). - Dave Rivers - -- [EMAIL PROTECTED]Work: (919) 676-0847 Get your mainframe programming tools at http://www.dignus.com To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 07:01:50 -0500, Thomas David Rivers wrote: Please, oh please, don't change that behavior in srand()/rand(). This subject is not discussed (again). We already discuss it long time ago and agrees that changes are allowed especially when they fix bugs. Search mailing lists for exact arguments. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 07:01:50AM -0500, Thomas David Rivers wrote: I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? That understanding is mistaken. I have worked with programs that depend on exactly that behavior. Then those programs have a bug. If you need every execution of the program to use the exact same sequence of pseudo-random numbers then the program need to implement its own RNG. That is, given the same input seed - I expect to see the same random sequence again. You will - if you generate both sequences during the same program execution. There are no guarantees (and has never been) that srand()/rand() will give the same sequence after an OS update or on a different system or even between two different runs of the same program. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... a) srand()/rand() does use different algorithms on different systems so depending on some particular algorithm is inherently unportable. b) random() was not introduced because the sequence from rand() couldn't be changed. It was rather because the calling interface for srand()/rand() puts constraints on the implementation that result in rand() by necessity being a rather poor RNG. random() was introduced so one could have a RNG with better statistical properties. c) I believe the algorithm used by rand() *was* changed in -CURRENT about two years ago. (And pretty the same discussion ensued back then.) This change was done because the old algorithm used was particularly poor and it was possible to do better. Now some defect in the new algorithm has apparently been discovered which is why it needs to be modified again. Please, oh please, don't change that behavior in srand()/rand(). - Dave Rivers - -- Insert your favourite quote here. Erik Trulsson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
Thus spake Thomas David Rivers [EMAIL PROTECTED]: I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? I have worked with programs that depend on exactly that behavior. That is, given the same input seed - I expect to see the same random sequence again. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... Please, oh please, don't change that behavior in srand()/rand(). There are two sides to this argument. One side says that rand() should always produce the same sequence for a given seed no matter what. This argument is bogus, because if you need exact reproducability across all platforms for all time, you should be using your own PRNG. The other side says that rand() should be a reasonably good RNG for most applications. It would be nice if things worked out that way, but there are enough broken rand() implementations out there that most people don't rely upon them. So I'd be inclined to call this argument bogus as well, except that I know someone who has been burned by a bad rand() while trying to test a randomized graph algorithm in C. My final thoughts are that having a better rand() implementation is a Good Thing, but it isn't that big a deal, and it certainly isn't worth all of this bickering. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
