Re: rand() is broken
On Sun, 2 Feb 2003, Juli Mallett wrote: > * De: David Malone <[EMAIL PROTECTED]> [ Data: 2003-02-02 ] > [ Subjecte: Re: rand() is broken ] > > On Sun, Feb 02, 2003 at 02:37:25PM -0800, Steve Kargl wrote: > > > FreeBSD Redhat SunOS > > > 660787754660787754645318364 > > > > FWIW - AIX aggrees with Solaris. > > Endiannes, or an SVR4 implementation difference? Not endianess, unless they did something really gross to the routine on Solatis/x86 > -- > Juli Mallett <[EMAIL PROTECTED]> > AIM: BSDFlata -- IRC: juli on EFnet > OpenDarwin, Mono, FreeBSD Developer > ircd-hybrid Developer, EFnet addict > FreeBSD on MIPS-Anything on FreeBSD > > To Unsubscribe: send mail to [EMAIL PROTECTED] > with "unsubscribe freebsd-current" in the body of the message > To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, 2 Feb 2003 [EMAIL PROTECTED] wrote: > In message <[EMAIL PROTECTED]>, "Andrey A. Chernov" writes: > >On Sun, Feb 02, 2003 at 19:32:50 +0100, [EMAIL PROTECTED] wrote: > >> > >> Anyway, last time we discussed this, I think we stuck with the rand() > >> we had because we feared that people were using it's repeatable well > >> documented sequence of random numbers in regression testing. > > > >As documented, it must be repeatable across the calls for same seed, that > >is all. It not means repeatable accross platforms or across different OS > >versions. In fact it is already not repeatable across different OS'es, so > >regression is limited. Also, regression must not stop bugs fixing progress > >in anycase. > > Our manual pages do not comprehensively list all compatibility > concerns or concessions, waving our manpage about does not address > the concern. > > As I said, I don't know how big a concern this is. But last time > it was enough of a concern to make us keep rand() as it was. > man srand on another system (for what its worth) says: The rand() function uses a multiplicative congruential random-number generator with period 2**32 that returns suc- cessive pseudo-random numbers in the range of 0 to RAND_MAX (defined in ). The srand() function uses the argument seed as a seed for a new sequence of pseudo-random numbers to be returned by sub- sequent calls to rand(). If srand() is then called with the same seed value, the sequence of pseudo-random numbers will be repeated. If rand() is called before any calls to srand() have been made, the same sequence will be generated as when srand() is first called with a seed value of 1. > Please surf the mail-archives to find the discussion, it contained > a lot of good arguments from both sides, arguments which should > be thought about before changing rand(). > > -- > Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 > [EMAIL PROTECTED] | TCP/IP since RFC 956 > FreeBSD committer | BSD since 4.3-tahoe > Never attribute to malice what can adequately be explained by incompetence. > > To Unsubscribe: send mail to [EMAIL PROTECTED] > with "unsubscribe freebsd-current" in the body of the message > To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, 2 Feb 2003, Andrey A. Chernov wrote: > On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: > > > > Why not? Arc4 is a) deterministic and b) good for all bits. > > If you mean arc4random() function - not, because it use true randomness, > if you mean RC4 algorithm, probably yes, but we should compare its > distribution with our current variant and be sure that speed is > acceptable. What form RC4 distribution have? > arc4 is the "non-encumbered" name for rc4 that is not derived from RSA code > -- > 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: rand() is broken
On Tue, Feb 04, 2003 at 17:36:04 +0300, Andrey A. Chernov wrote: > with a != 0 values are monotonically increased, I try with > a == 123459876 With your a == 62089911 (i.e. +1) the same: 0: 62089911 1: 124179822 2: 186269733 3: 248359644 4: 310449555 5: 372539466 6: 434629377 7: 496719288 8: 558809199 9: 620899110 With a == 0 the same: 0: 0 1: 62089911 2: 124179822 3: 186269733 4: 248359644 5: 310449555 6: 372539466 7: 434629377 8: 496719288 9: 558809199 Where is improvement? -- 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: rand() is broken
On Tue, Feb 04, 2003 at 15:22:03 +0100, Dag-Erling Smorgrav wrote: > > Yes we do. We get a better sequence for any given seed, i.e. we get > less correlation between n and x(n) for any given x(0). I don't think > it changes much for long sequences, but we get a better distribution > for short sequences (including short subsequences of long sequences). Maybe, I am not sure here, we need to ask expert. > As for patterns in the lower bits, we should try with a != 0 and see > how that affects the results. I believe the purpose of a in the LCG > algorithm is to scramble the lower bits. a != 0 eliminates 0 stuck problem, no additional visible effects. Even with a != 0 values are monotonically increased, I try with a == 123459876 0: 123459876 1: 185549787 2: 247639698 3: 309729609 4: 371819520 5: 433909431 6: 495999342 7: 558089253 8: 620179164 9: 682269075 -- 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: rand() is broken
On Tue, Feb 04, 2003 at 15:23:28 +0100, Dag-Erling Smorgrav wrote: > "Andrey A. Chernov" <[EMAIL PROTECTED]> writes: > > On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: > > > All that being said, adding 1 to *ctx before returning it (see patch) > > > adresses both of your objections: a seed of 0 will not cause the LCG > > > to get stuck, and the result of rand() will range between 0 and > > > RAND_MAX inclusive. > > Adding +1 you break algorithm formulae badly from math point of view, > > something else then given formulae not allowed here. You can change 'a' > > parameter to anything you want, but not add something at the end. > > Do the math - adding 1 after the modulo operation is equivalent to > setting a == k. Repeated k may affect distribution. Better variant will be with a != k. -- 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: rand() is broken
"Andrey A. Chernov" <[EMAIL PROTECTED]> writes: > On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: > > All that being said, adding 1 to *ctx before returning it (see patch) > > adresses both of your objections: a seed of 0 will not cause the LCG > > to get stuck, and the result of rand() will range between 0 and > > RAND_MAX inclusive. > Adding +1 you break algorithm formulae badly from math point of view, > something else then given formulae not allowed here. You can change 'a' > parameter to anything you want, but not add something at the end. Do the math - adding 1 after the modulo operation is equivalent to setting a == k. DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
"Andrey A. Chernov" <[EMAIL PROTECTED]> writes: > With NSHUFF 100 situation not changed much, so I beleive that stated > problem is common for this type PRNGs, so we gains nothing changing > formulae to Knuth-recommended values. Yes we do. We get a better sequence for any given seed, i.e. we get less correlation between n and x(n) for any given x(0). I don't think it changes much for long sequences, but we get a better distribution for short sequences (including short subsequences of long sequences). As for patterns in the lower bits, we should try with a != 0 and see how that affects the results. I believe the purpose of a in the LCG algorithm is to scramble the lower bits. DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:47:14 +0300, Andrey A. Chernov wrote: > On Tue, Feb 04, 2003 at 16:28:45 +0300, Andrey A. Chernov wrote: > > > > I'll produce working variant based on your patch... > > > > When all done correctly, there is repeated pattern still, so some NSHUFF > drop required too: > 1 7 e 4 a 0 7 d 3 a 0 6 > > See attached patch based on -current sources. > With NSHUFF 100 situation not changed much, so I beleive that stated problem is common for this type PRNGs, so we gains nothing changing formulae to Knuth-recommended values. -- 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: rand() is broken
On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: > I believe that's a feature. All linear congruence generator have a > fixed point. 0 is a far better fixed point than any other because it > is more "obviously unsuited" (for some values of "obviously") as a > seed value. (but see below) It is implementation details. rand() manpage says nothing about linear congruence generator and not suppose special meaning of 0 which means that application stuck at this point. We should not relay on that. > > The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. > > No, using modulo 0x8000 instead of modulo 0x7fff breaks the > algorithm. (but see below) Yes, but manpage says about range from 0 to RAND_MAX inclusive. It means that RAND_MAX clipping must be not part of algorithm and be applied only at later stage. > Changing RAND_MAX affects the algorithm in such a way that you should > not do so without giving serious thought to revising the algorithm Changing RAND_MAX should NOT affect algorithm at all, because RAND_MAX is not part of it. > All that being said, adding 1 to *ctx before returning it (see patch) > adresses both of your objections: a seed of 0 will not cause the LCG > to get stuck, and the result of rand() will range between 0 and > RAND_MAX inclusive. Adding +1 you break algorithm formulae badly from math point of view, something else then given formulae not allowed here. You can change 'a' parameter to anything you want, but not add something at the end. -- 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: rand() is broken
"Andrey A. Chernov" <[EMAIL PROTECTED]> writes:
> And the next bug is 32bit overflow there:
>
> tmp = *ctx * 62089911;
Ack, I thought the type promotion was automatic. Updated patch is
attached.
DES
--
Dag-Erling Smorgrav - [EMAIL PROTECTED]
Index: lib/libc/stdlib/rand.c
===
RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v
retrieving revision 1.11
diff -u -r1.11 rand.c
--- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:44:52 -
@@ -52,7 +52,7 @@
#endif /* TEST */
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -63,21 +63,23 @@
return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
/*
- * Compute x = (7^5 * x) mod (2^31 - 1)
- * wihout overflowing 31 bits:
- * (2^31 - 1) = 127773 * (7^5) + 2836
- * From "Random number generators: good ones are hard to find",
- * Park and Miller, Communications of the ACM, vol. 31, no. 10,
- * October 1988, p. 1195.
+ * New algorithm derived from
+ * The Laws of Cryptography: Pseudo-random Number Generation
+ * by Neal R. Wagner
+ * http://www.cs.utsa.edu/~wagner/laws/rng.html
+ * which itself is derived from work by Donald E. Knuth.
+ *
+ * This is a linear congruence generator using the equation
+ *
+ * x(n+1) = (k * x(n) + a) mod m
+ *
+ * where m is 2^31 - 1, k is 62089911 and a is 0.
*/
- long hi, lo, x;
+ uint64_t tmp;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x <= 0)
- x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = (uint64_t)*ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)0x7fff + 1);
+ return (*ctx);
#endif /* !USE_WEAK_SEEDING */
}
@@ -85,7 +87,7 @@
int
rand_r(unsigned int *ctx)
{
- u_long val = (u_long) *ctx;
+ uint32_t val = (uint32_t) *ctx;
int r = do_rand(&val);
*ctx = (unsigned int) val;
@@ -93,7 +95,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:28:45 +0300, Andrey A. Chernov wrote:
>
> I'll produce working variant based on your patch...
>
When all done correctly, there is repeated pattern still, so some NSHUFF
drop required too:
1 7 e 4 a 0 7 d 3 a 0 6
See attached patch based on -current sources.
--
Andrey A. Chernov
http://ache.pp.ru/
--- /usr/src/lib/libc/stdlib/rand.c Tue Feb 4 14:24:08 2003
+++ ./rand.cTue Feb 4 16:40:24 2003
@@ -51,10 +51,8 @@
#include
#endif /* TEST */
-#define NSHUFF 100 /* to drop part of seed -> 1st value correlation */
-
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -65,24 +63,25 @@
return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
/*
- * Compute x = (7^5 * x) mod (2^31 - 1)
- * wihout overflowing 31 bits:
- * (2^31 - 1) = 127773 * (7^5) + 2836
- * From "Random number generators: good ones are hard to find",
- * Park and Miller, Communications of the ACM, vol. 31, no. 10,
- * October 1988, p. 1195.
+ * New algorithm derived from
+ * The Laws of Cryptography: Pseudo-random Number Generation
+ * by Neal R. Wagner
+ * http://www.cs.utsa.edu/~wagner/laws/rng.html
+ * which itself is derived from work by Donald E. Knuth.
+ *
+ * This is a linear congruence generator using the equation
+ *
+ * x(n+1) = (k * x(n) + a) mod m
+ *
+ * where m is 2^31 - 1, k is 62089911 and a is 0.
*/
- long hi, lo, x;
+ uint64_t tmp;
/* Can't be initialized with 0, so use another value. */
if (*ctx == 0)
*ctx = 123459876;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x < 0)
- x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = ((uint64_t)*ctx * 62089911) % 2147483647;
+ return ((*ctx = tmp) % ((uint32_t)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
}
@@ -90,7 +89,7 @@
int
rand_r(unsigned int *ctx)
{
- u_long val = (u_long) *ctx;
+ uint32_t val = (uint32_t)*ctx;
int r = do_rand(&val);
*ctx = (unsigned int) val;
@@ -98,7 +97,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
@@ -110,11 +109,7 @@
srand(seed)
u_int seed;
{
- int i;
-
next = seed;
- for (i = 0; i < NSHUFF; i++)
- (void)do_rand(&next);
}
Re: rand() is broken
"Andrey A. Chernov" <[EMAIL PROTECTED]> writes:
> There is one bug in your patch: 0 is still illegal, so my fix required.
I believe that's a feature. All linear congruence generator have a
fixed point. 0 is a far better fixed point than any other because it
is more "obviously unsuited" (for some values of "obviously") as a
seed value. (but see below)
> The next bug is that there is % RAND_MAX + 1, not % RAND_MAX.
No, using modulo 0x8000 instead of modulo 0x7fff breaks the
algorithm. (but see below)
> The next is not the bug but portability thing alowing different RAND_MAX:
> you need to assign *ctx first and return it % RAND_MAX + 1 next, not
> assign *ctx % RAND_MAX + 1 like you currently does.
Changing RAND_MAX affects the algorithm in such a way that you should
not do so without giving serious thought to revising the algorithm
itself. In fact, RAND_MAX should be considered a characteristic of
the algorithm rather than a parameter that regulates it. For that
reason, and to make the algorithm more transparent to the reader, I've
replaced RAND_MAX with 0x7fff in the attached patch.
All that being said, adding 1 to *ctx before returning it (see patch)
adresses both of your objections: a seed of 0 will not cause the LCG
to get stuck, and the result of rand() will range between 0 and
RAND_MAX inclusive.
des@des ~/src% ./rndtest| head
2 0 1 7 1 7 f 2 5 3 f 6 a d 6 a 3 b 5 2 f 8 6 3 d 9 6 1 f 0 2 3
4 4 1 a f 3 b 5 4 2 a 6 f 0 0 6 9 5 1 7 c f 6 9 1 7 7 a 7 8 1 b
0 a c 7 a c 7 3 9 f 4 2 d 3 d 9 d 4 4 a 3 0 c f 7 6 2 5 9 2 3 7
5 b 7 7 f 9 9 b d 1 d c 5 2 b 6 7 c c 5 8 4 3 b 2 1 6 f 6 c 2 2
5 6 5 e a b b 8 e e 4 9 1 9 4 2 3 4 d b 3 5 3 a d 4 3 5 b 7 4 a
c 1 2 4 e 5 d 9 0 6 6 8 b 7 f 8 8 2 6 1 c d 1 c f f 0 9 1 3 4 c
5 6 8 b 8 9 a 8 5 d b 8 8 d 7 e 7 0 c 2 c 8 0 6 5 8 f 8 9 6 0 c
9 d 4 7 0 8 5 2 c b 8 e 5 f 5 c d 1 c c b 3 8 8 f f 1 2 a 5 c f
0 5 f 2 4 e 9 0 1 1 9 2 5 f 0 0 2 2 d f b f 7 0 2 a 2 4 7 a 2 f
9 0 f 1 c 8 e 2 f c f 2 8 c d 5 7 0 f 2 b a 2 a 4 d 8 b c 4 0 4
DES
--
Dag-Erling Smorgrav - [EMAIL PROTECTED]
Index: lib/libc/stdlib/rand.c
===
RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v
retrieving revision 1.11
diff -u -r1.11 rand.c
--- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:33:30 -
@@ -52,7 +52,7 @@
#endif /* TEST */
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -63,21 +63,23 @@
return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
/*
- * Compute x = (7^5 * x) mod (2^31 - 1)
- * wihout overflowing 31 bits:
- * (2^31 - 1) = 127773 * (7^5) + 2836
- * From "Random number generators: good ones are hard to find",
- * Park and Miller, Communications of the ACM, vol. 31, no. 10,
- * October 1988, p. 1195.
+ * New algorithm derived from
+ * The Laws of Cryptography: Pseudo-random Number Generation
+ * by Neal R. Wagner
+ * http://www.cs.utsa.edu/~wagner/laws/rng.html
+ * which itself is derived from work by Donald E. Knuth.
+ *
+ * This is a linear congruence generator using the equation
+ *
+ * x(n+1) = (k * x(n) + a) mod m
+ *
+ * where m is 2^31 - 1, k is 62089911 and a is 0.
*/
- long hi, lo, x;
+ uint64_t tmp;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x <= 0)
- x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = *ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)0x7fff + 1);
+ return (*ctx);
#endif /* !USE_WEAK_SEEDING */
}
@@ -85,7 +87,7 @@
int
rand_r(unsigned int *ctx)
{
- u_long val = (u_long) *ctx;
+ uint32_t val = (uint32_t) *ctx;
int r = do_rand(&val);
*ctx = (unsigned int) val;
@@ -93,7 +95,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:17:48 +0300, Andrey A. Chernov wrote: > On Tue, Feb 04, 2003 at 16:10:06 +0300, Andrey A. Chernov wrote: > > On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: > > > David Schultz <[EMAIL PROTECTED]> writes: > > > > You can do better than the present generator with 32 bits of state. > > > > See the following page by Neal Wagner (not to be confused with David Wagner): > > > > http://www.cs.utsa.edu/~wagner/laws/rng.html > > > > > > The attached patch, based on one of the m/k pairs suggested on that > > > page, results in the following: > > > > I just think about 62089911 and 48271 too :-) > > > > There is one bug in your patch: 0 is still illegal, so my fix required. > > The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. > > The next is not the bug but portability thing alowing different RAND_MAX: > you need to assign *ctx first and return it % RAND_MAX + 1 next, not > assign *ctx % RAND_MAX + 1 like you currently does. And the next bug is 32bit overflow there: tmp = *ctx * 62089911; must be tmp = (uint64_t) *ctx * 62089911; I'll produce working variant based on your patch... -- 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: rand() is broken
On Tue, Feb 04, 2003 at 16:10:06 +0300, Andrey A. Chernov wrote: > On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: > > David Schultz <[EMAIL PROTECTED]> writes: > > > You can do better than the present generator with 32 bits of state. > > > See the following page by Neal Wagner (not to be confused with David Wagner): > > > http://www.cs.utsa.edu/~wagner/laws/rng.html > > > > The attached patch, based on one of the m/k pairs suggested on that > > page, results in the following: > > I just think about 62089911 and 48271 too :-) > > There is one bug in your patch: 0 is still illegal, so my fix required. The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. The next is not the bug but portability thing alowing different RAND_MAX: you need to assign *ctx first and return it % RAND_MAX + 1 next, not assign *ctx % RAND_MAX + 1 like you currently does. -- 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: rand() is broken
On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: > David Schultz <[EMAIL PROTECTED]> writes: > > You can do better than the present generator with 32 bits of state. > > See the following page by Neal Wagner (not to be confused with David Wagner): > > http://www.cs.utsa.edu/~wagner/laws/rng.html > > The attached patch, based on one of the m/k pairs suggested on that > page, results in the following: I just think about 62089911 and 48271 too :-) There is one bug in your patch: 0 is still illegal, so my fix required. -- 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: rand() is broken
On Tue, Feb 04, 2003 at 15:07:30 +0300, Andrey A. Chernov wrote: > On Tue, Feb 04, 2003 at 03:52:37 -0800, David Schultz wrote: > > > > You can do better than the present generator with 32 bits of state. > > See the following page by Neal Wagner (not to be confused with David Wagner): > > http://www.cs.utsa.edu/~wagner/laws/rng.html > > The section on LCGs suggests that the multiplier FreeBSD uses (7^5) > > is not particularly good, and points out some better values suggested > > by Knuth. I can't find the original discussion in TAOCP vol. 2, but Two variants looks interesting from that paper: m=2^31-1, k=48271 m=2^31-1, k=62089911 Do you know any comparison of them with what we currently have, i.e. m=2^31-1, k=16807 -- 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: rand() is broken
David Schultz <[EMAIL PROTECTED]> writes:
> You can do better than the present generator with 32 bits of state.
> See the following page by Neal Wagner (not to be confused with David Wagner):
> http://www.cs.utsa.edu/~wagner/laws/rng.html
The attached patch, based on one of the m/k pairs suggested on that
page, results in the following:
des@des ~/src% ./rndtest | head
0 b 5 f 8 5 2 c 8 5 1 8 4 9 7 b d 9 e a d 3 8 8 5 9 2 3 e a c f
7 a d b f 0 1 3 6 7 4 f 0 6 0 1 2 3 1 c b a 6 1 e 0 9 c f 7 c 6
6 1 a a d b 3 e b a a 0 e d a f 8 6 3 f f 9 3 7 6 6 d 7 f 6 8 d
b d 6 2 b f 2 2 b 1 7 4 4 3 5 5 2 9 6 4 e 1 9 4 7 b f 6 f 7 8 c
1 5 7 e 3 5 d b 8 c c 4 d 1 3 6 e 0 3 3 3 2 e 5 3 b 5 e 7 b c a
0 a 3 2 d 5 f c 9 f c 3 9 a 1 f 3 f 2 c 5 9 4 6 2 d 2 3 e 2 7 5
a 8 8 1 5 7 0 5 4 e c f 6 3 b 0 8 4 d 2 a 8 0 5 7 b 2 1 4 e e 9
7 1 5 5 6 f f e 6 f a 4 e 5 a f 8 d f 7 b 3 8 d e 3 f 5 4 0 2 e
5 c a f 5 a e 5 0 9 4 6 0 0 9 f d 9 6 4 b f 8 2 3 5 e 4 5 9 9 a
d 3 4 5 5 0 f 9 9 1 8 6 7 a 5 0 2 0 5 8 b 6 1 6 7 f a 9 a 6 6 d
Note that my patch assumes that RAND_MAX fits in 32 bits, which should
be acceptable for FreeBSD since it always uses 32-bit ints (all our
32-bit platforms are ILP32, and I believe all our 64-bit platforms are
I32LP64) and RAND_MAX is uniformly defined to 0x7fff.
DES
--
Dag-Erling Smorgrav - [EMAIL PROTECTED]
Index: lib/libc/stdlib/rand.c
===
RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v
retrieving revision 1.11
diff -u -r1.11 rand.c
--- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:37:03 -
@@ -52,7 +52,7 @@
#endif /* TEST */
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -63,21 +63,23 @@
return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
/*
- * Compute x = (7^5 * x) mod (2^31 - 1)
- * wihout overflowing 31 bits:
- * (2^31 - 1) = 127773 * (7^5) + 2836
- * From "Random number generators: good ones are hard to find",
- * Park and Miller, Communications of the ACM, vol. 31, no. 10,
- * October 1988, p. 1195.
+ * New algorithm derived from
+ * The Laws of Cryptography: Pseudo-random Number Generation
+ * by Neal R. Wagner
+ * http://www.cs.utsa.edu/~wagner/laws/rng.html
+ * which itself is derived from work by Donald E. Knuth.
+ *
+ * This is a linear congruence generator using the equation
+ *
+ * x(n+1) = (k * x(n) + a) mod m
+ *
+ * where m is 2^31 - 1, k is 62089911 and a is 0.
*/
- long hi, lo, x;
+ uint64_t tmp;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x <= 0)
- x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = *ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)RAND_MAX);
+ return (*ctx);
#endif /* !USE_WEAK_SEEDING */
}
@@ -85,7 +87,7 @@
int
rand_r(unsigned int *ctx)
{
- u_long val = (u_long) *ctx;
+ uint32_t val = (uint32_t) *ctx;
int r = do_rand(&val);
*ctx = (unsigned int) val;
@@ -93,7 +95,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
Re: rand() is broken
On Tue, Feb 04, 2003 at 03:52:37 -0800, David Schultz wrote: > > You can do better than the present generator with 32 bits of state. > See the following page by Neal Wagner (not to be confused with David Wagner): > http://www.cs.utsa.edu/~wagner/laws/rng.html > The section on LCGs suggests that the multiplier FreeBSD uses (7^5) > is not particularly good, and points out some better values suggested > by Knuth. I can't find the original discussion in TAOCP vol. 2, but Thank for your pointer, I'll look at later. > Well, if 0 doesn't work, and 10 doesn't work, and 100 doesn't > work, then I'm not too hopeful about 2000. I appeal to Asimov's > zero, one, infinity law. I found that f.e. 50 is worse than 100, but 200 isn't better. 100 is better than 0 because remove monotonically increased sequence. -- 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: rand() is broken
Thus spake Andrey A. Chernov <[EMAIL PROTECTED]>: > On Mon, Feb 03, 2003 at 21:40:20 -0800, David Schultz wrote: > I don't try to make rand() good for high-quality pseudo-randomness, > because it can be done by price of speed and, more important, big state > size. Due to rand_r() restriction state size can be one word only, so we > can choose rand() algorithm only from those which pass this > restrictions. You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The section on LCGs suggests that the multiplier FreeBSD uses (7^5) is not particularly good, and points out some better values suggested by Knuth. I can't find the original discussion in TAOCP vol. 2, but I take N. Wagner's word that the numbers have been blessed by the holy hand of Knuth. I'm sure you can find more information if you search the literature. I apologize, but I don't have time to help you right now, and rand() isn't really a concern to me. > Returning to current algorithm, I am interested in good NSHUFF value in > the range 100-2000. Do you have any findings there? Well, if 0 doesn't work, and 10 doesn't work, and 100 doesn't work, then I'm not too hopeful about 2000. I appeal to Asimov's zero, one, infinity law. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 12:58:40 +0300, Andrey A. Chernov wrote: > On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: > > > > Returning to current algorithm, I am interested in good NSHUFF value in > > the range 100-2000. Do you have any findings there? > > Apparently 100 is not enough too, I see repeated pattern in your > program. I'll try other values... Well, I find that bigger values are not better, it means that algorithm limit is reached, so just 100 is good enough... -- 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: rand() is broken
On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: > > So, if you define USE_WEAK_SEEDING and re-compile rand.c, you'll get even > worse results from your test. It means current variant is better then > previous. If you know even better algorithm wich pass restrictions above, > just tell and we consider switching to it. Here is result from your test for USE_WEAK_SEEDING, i.e. for old algorithm. As we can see, it even worse than current one. It means that returning to old algoritm as Kris means (maybe?) is not an option. 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 -- 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: rand() is broken
On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: > > Returning to current algorithm, I am interested in good NSHUFF value in > the range 100-2000. Do you have any findings there? Apparently 100 is not enough too, I see repeated pattern in your program. I'll try other values... -- 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: rand() is broken
On Mon, Feb 03, 2003 at 21:40:20 -0800, David Schultz wrote: > followed by a 5 or 6. There is a similar pattern for 'e a 7'. I > think this pretty much demonstrates that the algorithm isn't good > enough to generate high-quality randomness with respect to > different seed values. I'm not suggesting that it absolutely must > be replaced, since most rand() implementations aren't very good in > the first place, but I'm pointing out that to do a good job of > fixing it once and for all is harder than you might think. I don't try to make rand() good for high-quality pseudo-randomness, because it can be done by price of speed and, more important, big state size. Due to rand_r() restriction state size can be one word only, so we can choose rand() algorithm only from those which pass this restrictions. So, if you define USE_WEAK_SEEDING and re-compile rand.c, you'll get even worse results from your test. It means current variant is better then previous. If you know even better algorithm wich pass restrictions above, just tell and we consider switching to it. Returning to current algorithm, I am interested in good NSHUFF value in the range 100-2000. Do you have any findings there? -- 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: rand() is broken
Thus spake Eric Hodel <[EMAIL PROTECTED]>: > David Schultz ([EMAIL PROTECTED]) wrote: > > > Rather than me showing you more semi-meaningful numbers from > > Marsaglia's tests, why don't you look at the following sequence, > > which I get by taking the lowest four bits of the 201st number in > > the rand() sequence for seeds of (0, 1, 2, ...). > > > > f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 > f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 > f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 > f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 > f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 > f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 > f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 > f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 > f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 > f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 > f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 > f > > > Notice that 'f c 9' repeats in regular intervals and is always > > followed by a 5 or 6. There is a similar pattern for 'e a 7'. I > > think this pretty much demonstrates that the algorithm isn't good > > enough to generate high-quality randomness with respect to > > different seed values. I'm not suggesting that it absolutely must > > be replaced, since most rand() implementations aren't very good in > > the first place, but I'm pointing out that to do a good job of > > fixing it once and for all is harder than you might think. > > A littele modification shows just how similar these sequences are :) Yeah, I saw the periodicity when I asked less(1) to select particular subsequences. I guess it's a bit more impressive when you select the right modulus. ;-) To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
David Schultz ([EMAIL PROTECTED]) wrote: > Rather than me showing you more semi-meaningful numbers from > Marsaglia's tests, why don't you look at the following sequence, > which I get by taking the lowest four bits of the 201st number in > the rand() sequence for seeds of (0, 1, 2, ...). > f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f > Notice that 'f c 9' repeats in regular intervals and is always > followed by a 5 or 6. There is a similar pattern for 'e a 7'. I > think this pretty much demonstrates that the algorithm isn't good > enough to generate high-quality randomness with respect to > different seed values. I'm not suggesting that it absolutely must > be replaced, since most rand() implementations aren't very good in > the first place, but I'm pointing out that to do a good job of > fixing it once and for all is harder than you might think. A littele modification shows just how similar these sequences are :) -- Eric Hodel - [EMAIL PROTECTED] - http://segment7.net All messages signed with fingerprint: FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04 msg51721/pgp0.pgp Description: PGP signature
Re: rand() is broken
Thus spake Andrey A. Chernov <[EMAIL PROTECTED]>:
> On Sun, Feb 02, 2003 at 16:26:39 -0800, David Schultz wrote:
> >
> > The correlation is still present with your patch and NSHUFF set to
> > 10. For instance, try seeding rand() with contiguous monotonically
> > increasing integers, and observe the four lowest-order bits.
>
> Since you already have running framework for that, could you please
> test it with NSHUFF picked from 100-2000 range?
Rather than me showing you more semi-meaningful numbers from
Marsaglia's tests, why don't you look at the following sequence,
which I get by taking the lowest four bits of the 201st number in
the rand() sequence for seeds of (0, 1, 2, ...).
f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9
6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f
c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5
2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b
8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1
e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7
4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d
a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3
0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9
6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f
Notice that 'f c 9' repeats in regular intervals and is always
followed by a 5 or 6. There is a similar pattern for 'e a 7'. I
think this pretty much demonstrates that the algorithm isn't good
enough to generate high-quality randomness with respect to
different seed values. I'm not suggesting that it absolutely must
be replaced, since most rand() implementations aren't very good in
the first place, but I'm pointing out that to do a good job of
fixing it once and for all is harder than you might think.
The program to generate this sequence follows. I ran this on a
several-month-old -CURRENT system with the new generator, but
without your latest patches.
#include
#include
int main() {
int i, j;
for (i = 0; ; i++) {
srand(i);
for (j = 0; j < 200; j++)
rand();
printf("%x ", rand() & 0x0f);
if (i % 32 == 31)
putchar('\n');
}
}
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Brad Knowles wrote: > At 4:41 PM -0800 2003/02/02, Terry Lambert wrote: > > Donald Knuth seemed to like them well enough to publish the > > algorithm, as part of his discussion on randomness. He *didn't* > > publish RC4, in that same discussion. > > RC stands for Ron's Code. This stuff came after the work that > Diffie Hellman did, for which the patent expired a little while ago. > Did RC4 even exist at the time that Don published that book? Not the original edition, but yes, for the revised edition, which is only a couple of years old, and, in fact, includes some new algorithms, based on the fact that Fermat's last Theorem has been proved, proving the Taniyama-Shimura Conjecture as a side effect, etc.. -- Terry 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
Re: rand() is broken
Bakul Shah <[EMAIL PROTECTED]> writes: > Guys, please realize that random() is also used in generating > simulation inputs (or timing or whatever). If you go change > the underlying algorithm or its parameters one can't generate > the same sequence from the same seed when repeating a test. > Some chip bug symptoms show up after hours/days of simulation > time and only with specific inputs so repeatablity is a > requirement. Go to http://stat.fsu.edu/pub/diehard/cdrom/> for free download of up to 480,000,000 random bits, which ought to be enough for most simulations. DES -- Dag-Erling Smorgrav - [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)
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 - -- 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)
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)
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
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
#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 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 14:26:00 +0300, Andrey A. Chernov wrote: > > random(3) is not affected to to its hashing nature. We talk about rand(3). to to = due to -- 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 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 11:19:17 +, Mark Murray wrote: > > "simple test"? > > How long did you check for? See my another message with details. > random() is documented to not repeat before some number of outputs; > how do you know that this fix does not significantly shorten that? random(3) is not affected to to its hashing nature. We talk about rand(3). -- 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 0 problem (was Re: rand() is broken)
"Andrey A. Chernov" writes: > On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: > > > > How do you _know_ that your newly chosen magic number isn't going to cause > > some kind of recurring (and too-short) sequence of numbers? > > I run simple test for it, it is not too short. "simple test"? How long did you check for? random() is documented to not repeat before some number of outputs; how do you know that this fix does not significantly shorten that? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 14:08:41 +0300, Andrey A. Chernov wrote: > On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: > > > > How do you _know_ that your newly chosen magic number isn't going to cause > > some kind of recurring (and too-short) sequence of numbers? > > I run simple test for it, it is not too short. To be more specific - it never returns to 0 from this value at least in 2**31 iterations. You can test it by yourself, the code is obvious: srand(0) ... loop ... if (rand() == 0) print iteration number -- 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 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: > > How do you _know_ that your newly chosen magic number isn't going to cause > some kind of recurring (and too-short) sequence of numbers? I run simple test for it, it is not too short. -- 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 0 problem (was Re: rand() is broken)
"Andrey A. Chernov" writes: > > If I understand correctly, this still doesn't solve the problem, > > because any PRNG sequence that hits the "magic" value will still get > > stuck there forever. > > It was true for the first patch I post which just move problem to another= > > place (this is commonly spreaded method for this PRNG). > > It is false for the last patch I post which not stuck with any given seed. How do you _know_ that your newly chosen magic number isn't going to cause some kind of recurring (and too-short) sequence of numbers? Will it recur after 5 iterations? 100? 1000? 100? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> > > FWIW - AIX aggrees with Solaris. OSF1 .. V5.1 732 alpha HP-UX . B.11.00 U 9000/800 agree with Solaris -- Alexander Pohoyda <[EMAIL PROTECTED]> To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
At 4:41 PM -0800 2003/02/02, Terry Lambert wrote: Donald Knuth seemed to like them well enough to publish the algorithm, as part of his discussion on randomness. He *didn't* publish RC4, in that same discussion. RC stands for Ron's Code. This stuff came after the work that Diffie Hellman did, for which the patent expired a little while ago. Did RC4 even exist at the time that Don published that book? -- Brad Knowles, <[EMAIL PROTECTED]> "They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, Historical Review of Pennsylvania. GCS/IT d+(-) s:+(++)>: a C++(+++)$ UMBSHI$ P+>++ L+ !E-(---) W+++(--) N+ !w--- O- M++ V PS++(+++) PE- Y+(++) PGP>+++ t+(+++) 5++(+++) X++(+++) R+(+++) tv+(+++) b+() DI+() D+(++) G+() e++> h--- r---(+++)* z(+++) To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 16:26:39 -0800, David Schultz wrote: > > The correlation is still present with your patch and NSHUFF set to > 10. For instance, try seeding rand() with contiguous monotonically > increasing integers, and observe the four lowest-order bits. Since you already have running framework for that, could you please test it with NSHUFF picked from 100-2000 range? -- 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: rand() is broken
* De: David Malone <[EMAIL PROTECTED]> [ Data: 2003-02-03 ]
[ Subjecte: Re: rand() is broken ]
> > > FWIW - AIX aggrees with Solaris.
>
> > Endiannes, or an SVR4 implementation difference?
>
> OS X agrees with FreeBSD i386. In fact, FreeBSD sparc64 and FreeBSD
> alpha are all the same too, so it seems the code isn't too sensitive
> to byteorder or wordsize.
>
> Bakul's comments on who agrees with BSD 4.{2,3,4}-* probably explain
> the differences.
*Nod* when I saw that message, I got it :)
--
Juli Mallett <[EMAIL PROTECTED]>
AIM: BSDFlata -- IRC: juli on EFnet
OpenDarwin, Mono, FreeBSD Developer
ircd-hybrid Developer, EFnet addict
FreeBSD on MIPS-Anything on FreeBSD
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> > FWIW - AIX aggrees with Solaris.
> Endiannes, or an SVR4 implementation difference?
OS X agrees with FreeBSD i386. In fact, FreeBSD sparc64 and FreeBSD
alpha are all the same too, so it seems the code isn't too sensitive
to byteorder or wordsize.
Bakul's comments on who agrees with BSD 4.{2,3,4}-* probably explain
the differences.
David.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Steve Kargl wrote: > On Sun, Feb 02, 2003 at 04:37:07PM -0800, Terry Lambert wrote: > > I can fire up my HP/UX and SunOS 4.1.3-U1 boxes too, if you need > > those, but I'm pretty sure the reason you got a different answer > > for newer Solaris was because it uses the SVR4 code, instead. > > That's the whole point! You should not expect the > output from random() for a given seed to produce the > same sequence of numbers on different platforms. No, the point is that *you* think I should not expect it, when historically, whether I *should* or not, I've been able to. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Edward Brocklesby wrote: > On Monday 03 February 2003 12:20 am, Terry Lambert wrote: > > Edward Brocklesby wrote: > > > Where was it indicated that random() wouldn't change? > > > > Right there in the boot message, and again when you logged in, > > where the system indicated to you that it was a BSD system; > > Sorry, I can't quite work out what you mean by this. Are you saying that it's > assumed random()'s API won't changed because it's guaranteed by BSD? Some behaviours are assumed to remain constant across BSD systems, which give the system it's "BSD flavor". For me, the random number generators have always been one of these. Personally, I'm concened about being able to repeat physics simulations that use drand48(), the code for the pair production coming from out of Berkeley, as well. So long as the algorithm doesn't change, the results obtained in 1982 are going to be repeatable at any point in the future. This is needed, if you intend to be able to build on published work that used a transformation of the raw numbers out of the simulation, and you need the same raw numbers, in order to do it. The experiment, in other words, needs to be repeatable. Basically, for simulations results like this, where the results are pair productions which are then kept or thrown away, based on whether the particular pair production is "possible", given the theorized physics, changing the random number generator is morally equivalent to changing the data from accelerator experiments, after the fact. Lucent just fired a PhD, very loudly and publically, for that type of number-fudging. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Don wrote: > > > It isn't a question of the API. It's a question of expected function > > > output. > > > > Then it's applicable not only to binary packages as Terry states, but any > > source that uses rand(). > > I think Terry mentioned binary packages simply because it is harder to fix > them than something available as source but I could be mistaken. I mentioned them because they are impossible to fix without hacking the system libc.so, whereas with source, you can recompile the code and override the libc version with your own. LD_PRELOAD could be used, if the interface is unchanged, and the saved state area is not managed promiscuously anywhere. The main problem is new code that depends on new behaviour conflicting with old code that depends on old behaviour. A number of the ASIC packages Bakul *may* be using come precompiled from the vendor, without source code (and yes, they have FreeBSD versions available, when you are slinging that kind of money around). > > I would say that depending on the internal algorithm used by rand() (or > > random()) is a bad idea; however, I don't know what the relevant standards > > say about this, so I won't say any further. > > > > (Why is it a bad idea? Because I'm not going to write software which makes > > this assumption; I'm sure that even if at some point in time all systems use > > an identical algorithm, at some point my software will have to run on a > > system which uses something different. So if I really need it, I will take > > rand() from libc and place it in my own code.) > > If only all developers were as good as you we would not have a problem. Heh. If they were, this would not be an issue in the first place, because they would not be using the system random number generators from libc, and so they would see no reason to fix them. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Monday 03 February 2003 12:41 am, Don wrote: > I think Terry mentioned binary packages simply because it is harder to fix > them than something available as source but I could be mistaken. Possibly -- if we're looking at this from the point of view of the user of said binary package, rather than the developer (as I'd assumed), then I see what you mean (you can do ld hacks and so on, but ..) > > I'm not sure Yet Another RNG API (of course arc4random() already exists) > > gains anything unless rand()/random() absolutely cannot be changed; and > > as I say I'm not convinced this is the case. > > I am by no means convinced either. I do, however, think this is something > that should not be changed without a lot of consideration and testing. IMHO, it "shouldn't" break things (ie, things shouldn't be relying on it); but, well, I can accept there might be something that does. I do find it hard to believe though; this 'simulation' problem is the first I've heard of it, and it doesn't look like an insurmountable one. > Your point about arc4random() is a good one. Why depend on rand() for > cryptographic randomness when we already have arc4random()? Because arc4random() is not portable. I would rather rely on the OS having a useful rand() RNG rather than #ifdef'ing on this that and the other to choose the correct one. > > Doesn't even the 0 / RAND_MAX fix change > > the algorithm? Software which relies on that behaviour will break .. > > [...] I don't recall advocating that change either. Well, no -- but are you against it? Where is the line drawn? Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Terry Lambert wrote: > > Last 10 digits. > > > > FreeBSD Redhat SunOS > 386BSD 0.1+ > patchkitTRU64 Crap. Ignore these numbers. I replaced the libc implementation on both these machines, and forgot I had done it. When I put the code back to what it was, they give the Solaris numbers. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 04:37:07PM -0800, Terry Lambert wrote: > > I can fire up my HP/UX and SunOS 4.1.3-U1 boxes too, if you need > those, but I'm pretty sure the reason you got a different answer > for newer Solaris was because it uses the SVR4 code, instead. > That's the whole point! You should not expect the output from random() for a given seed to produce the same sequence of numbers on different platforms. -- Steve To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Mark Murray wrote: > > That's why randomness tests + mathematician to interpretate their results > > are needed to compare what we have now in random(3) with RC4. Easy and > > understandable code not always mean better results. We can't switch > > algorithms blindly, i.e. when their comparative quality remains unknown. > > Actually, RC4 is well understood (and trusted). LCRNG's are considered > less good in comparison with cryptographic techniques. There is too much > to go wrong in them (as you have just discovered!) :-) Donald Knuth seemed to like them well enough to publish the algorithm, as part of his discussion on randomness. He *didn't* publish RC4, in that same discussion. Cryptographic uses are a small percentage of the real-world use for PRNG's. If you are worried about cryptographic strength, then you shouldn't be using a libc function. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Monday 03 February 2003 12:20 am, Terry Lambert wrote: > Edward Brocklesby wrote: > > Where was it indicated that random() wouldn't change? > > Right there in the boot message, and again when you logged in, > where the system indicated to you that it was a BSD system; Sorry, I can't quite work out what you mean by this. Are you saying that it's assumed random()'s API won't changed because it's guaranteed by BSD? Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> > It isn't a question of the API. It's a question of expected function > > output. > > Then it's applicable not only to binary packages as Terry states, but any > source that uses rand(). I think Terry mentioned binary packages simply because it is harder to fix them than something available as source but I could be mistaken. > I would say that depending on the internal algorithm used by rand() (or > random()) is a bad idea; however, I don't know what the relevant standards > say about this, so I won't say any further. > > (Why is it a bad idea? Because I'm not going to write software which makes > this assumption; I'm sure that even if at some point in time all systems use > an identical algorithm, at some point my software will have to run on a > system which uses something different. So if I really need it, I will take > rand() from libc and place it in my own code.) If only all developers were as good as you we would not have a problem. > > A seperate function for those who need cryptographic randomness seems like > > a _much_ better idea. > > I'm not sure Yet Another RNG API (of course arc4random() already exists) gains > anything unless rand()/random() absolutely cannot be changed; and as I say > I'm not convinced this is the case. I am by no means convinced either. I do, however, think this is something that should not be changed without a lot of consideration and testing. Your point about arc4random() is a good one. Why depend on rand() for cryptographic randomness when we already have arc4random()? > Doesn't even the 0 / RAND_MAX fix change > the algorithm? Software which relies on that behaviour will break .. Any software which always needs to get back maxint when it calls rand() is hopelessly broken :) Besides which, I don't recall advocating that change either. -Don To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Steve Kargl wrote:
> I was going to stay out of this, but
>
> #include
> #include
> int main(void) {
> int i;
> long x;
> x = 100L;
> srandom(x);
> for (i = 0; i < 1010; i++) {
> x = random();
> printf("%ld\n", x);
> }
> return 0;
> }
>
> Last 10 digits.
>
> FreeBSD Redhat SunOS
> 660787754660787754645318364
> 3275486913275486911583150371
> 2009993994 2009993994 715222008
> 1653966416 1653966416 1349166998
> 1074113008 1074113008 566227131
> 2142626740 2142626740 1382825076
> 1517775852 1517775852 583981903
> 1453318125 1453318125 1453942393
> 6196078076196078071952958724
> 1999863931999863931599163286
386BSD 0.1+
patchkitTRU64
660787754 660787754
327548691 327548691
2009993994 2009993994
1653966416 1653966416
1074113008 1074113008
2142626740 2142626740
1517775852 1517775852
1453318125 1453318125
619607807 619607807
199986393 199986393
I can fire up my HP/UX and SunOS 4.1.3-U1 boxes too, if you need
those, but I'm pretty sure the reason you got a different answer
for newer Solaris was because it uses the SVR4 code, instead.
The *48() functions are also identical (linear congruential); I
used to use them for physics simulations. The f2c compiler did
not have the functions until I personally added them to the
library.
-- Terry
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Thus spake Andrey A. Chernov <[EMAIL PROTECTED]>: > On Sat, Feb 01, 2003 at 23:06:50 -0800, Kris Kennaway wrote: > > FreeBSD's rand() implementation has been broken for the past 23 > > months, since the following commit: > > > i.e. the first value returned from rand() is correlated with the seed > > given to srand(). This is a big problem unless your seed is randomly > > chosen over its entire integer range. I noticed this because awk > > exhibits the same problem, and the script seeds the generator with a > > PID. The script works fine under 4.x since the rand() implementation > > does not have this "feature". > > Yes, first value correlation is there, but old formulae have even worse > effect "The random sequences do not vary much with the seed", as source > file comments and whole discussion about old RNG bad effects shown. I.e. > for different time+PID sequence, especially increased monotonically, like > in common practice, you'l got the same random sequence with old formulae > (which can't be called "works fine" because this fine work was the main > reason for change). So, returning to old formulae is not an option. > > The real problem is not in formulae, but in srand() funclion. This simple > patch can fix first value correlation, and I plan to commit it, if we all > agree. I not find better value for NSHUFF right now, but think > that something like 10 will be enough to fight corellation completely. > Some generating picture tests needed. The correlation is still present with your patch and NSHUFF set to 10. For instance, try seeding rand() with contiguous monotonically increasing integers, and observe the four lowest-order bits. Just for the heck of it, I ran Marsaglia's tests on the rand() implementation in -CURRENT. The arc4random() implementation passed with flying colors as expected, whereas rand() seems to have some slight defects, particularly in the lowest and highest order bits. When I looked at rand()'s behavior with respect to different seeds, it failed miserably, both with and without your patch. The results are available at http://www.csua.berkeley.edu/~das/marsaglia/ I'm not necessarily advocating changing the algorithm at all, given that it's well known that many rand() implementations are not very random. But I also don't buy the argument that ``rand() should never ever change.'' If someone wants to do the work to improve the algorithm, that's fine with me. David Wagner has collected some links on randomness that might be helpful: http://www.cs.berkeley.edu/~daw/rnd/index.html To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Monday 03 February 2003 12:18 am, Don wrote: > It isn't a question of the API. It's a question of expected function > output. Then it's applicable not only to binary packages as Terry states, but any source that uses rand(). > I run FreeBSD and not Linux because of the stability and predictability of > the system. Changing a critical function like rand() when we know that > there are applications which depend on its output I would say that depending on the internal algorithm used by rand() (or random()) is a bad idea; however, I don't know what the relevant standards say about this, so I won't say any further. (Why is it a bad idea? Because I'm not going to write software which makes this assumption; I'm sure that even if at some point in time all systems use an identical algorithm, at some point my software will have to run on a system which uses something different. So if I really need it, I will take rand() from libc and place it in my own code.) > does not seem like a good idea. > > A seperate function for those who need cryptographic randomness seems like > a _much_ better idea. I'm not sure Yet Another RNG API (of course arc4random() already exists) gains anything unless rand()/random() absolutely cannot be changed; and as I say I'm not convinced this is the case. Doesn't even the 0 / RAND_MAX fix change the algorithm? Software which relies on that behaviour will break .. > This is my person opinion. I am not a developer so please take my comments > as such. Likewise. Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Doug Barton <[EMAIL PROTECTED]> wrote: > >I can think of one significant benefit... I had noticed that my perl >script to pick random windowmaker themes (which uses rand()) seemed to be >picking the same themes over and over again. That's a bug in perl's compile-time configuration. It can be told to use something better. See PR 25794. Tony. -- f.a.n.finch <[EMAIL PROTECTED]> http://dotat.at/ LANDS END TO ST DAVIDS HEAD INCLUDING THE BRISTOL CHANNEL: WEST 6 TO GALE 8. EASING WEST 5 OR 6 MONDAY MORNING. WEST OR NORTHWEST 6 OR 7 AGAIN LATER. RAIN OR SHOWERS, MAINLY FAIR PERHAPS MORE ISOLATED SHOWERS MONDAY. MAINLY GOOD. ROUGH OR VERY ROUGH. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Doug Barton wrote: > I can think of one significant benefit... I had noticed that my perl > script to pick random windowmaker themes (which uses rand()) seemed to be > picking the same themes over and over again. Now I know why. :) I had to > create a "last seen" list to artificially increase the "randomness." Oh > wait, TWO benefits... xscreensaver is having the same problem. Use /dev/random. You have to get some benefit back from it making all your interrupt handlers just that much slower so it could "harvest entropy" ``for'' you... -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Edward Brocklesby wrote: > On Sunday 02 February 2003 8:39 pm, Bakul Shah wrote: > > What I am suggesting is to leave random() as it is and > > guarantee its behavior won't change and add cryto_random() or > > whatever, and indicate it *may* change. > > Where was it indicated that random() wouldn't change? Right there in the boot message, and again when you logged in, where the system indicated to you that it was a BSD system; the same notification that told you the resolved code is present in libc, the shared library implementation doesn't allocate specific chunks of UVM so the libraries can have their symbols resolved to fixed offsets instead of using PIC, that libc contains qsort(), etc.. Technically, it should be telling you that the SA_RESTART flag is present by default on signal handlers, too, so that you can more easily write a user space threads implementation using wrapper functions, and save a masking and unmasking system call for each potentially blocking call, but that's been broken for a long time, now, because of putative POSIX(SVID) compliance. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> > Binary packages from third party software vendors. > > What about them? They either, > a) link to a static libc, and use its rand() always; or > b) link to a shared libc, and use its rand(), as the binary API hasn't > changed; or It isn't a question of the API. It's a question of expected function output. > c) if they really need their own specific RNG, they include it themselves, and > don't rely on libc at all. > > So I fail to see the problem here. The opinion of a random user: I run FreeBSD and not Linux because of the stability and predictability of the system. Changing a critical function like rand() when we know that there are applications which depend on its output does not seem like a good idea. A seperate function for those who need cryptographic randomness seems like a _much_ better idea. This is my person opinion. I am not a developer so please take my comments as such. -Don To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> Interesting The SunOS output exactly matches random(3) > behavior from 4.3BSD! In fact random() remained the same for > 4.3BSD-Reno, -Tahoe, 4.4BSD-Alpha and Net2. > > 4.2BSD random() behavior is different from all of the above. > There was real bug-fix between 4.2BSD and 4.3BSD. > > I don't know when the FreeBSD/Redhat change was made or if it > broke any statistical properties. FYI: The FreeBSD change was made in -r1.4 of random.c by Andrey in Oct 1996. The previous version of random.c behaves exactly the same as the one in 4.3BSD, SunOS and AIX. I am sorry I was too busy with other things then and missed this change. Andrey refers to an OCT 1988 CACM paper by Park & Miller "Random number generators: good ones are hard to find" as a justification for this change. Also FYI: NetBSD random(3) matches the 4.3BSD random(). Haven't checked OpenBSD. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Mark Murray wrote: > Bakul Shah writes: > > random(3) also provides an initstate() call which presumably > > allows you to change the amount of randomnes. So here is > > another suggestion: why not fold your algorithm change in > > that function? For example, > > > > initstate(seed, "RC4", 3); > > > > changes the algorithm to RC4. Yes, this is a change in the > > interface but one I am sure most people can live with. > > No. Evil interface change. #ifdef hell while programs try to > figure out OS differences. Definitely agree. Interface changes are bad. > If an os provides a function, that function should be as good > as possible while not breaking standards. There are standards, and there are defacto standards. I really like the idea of a crypto_random() (and a crypto_rand()) that the weenies who want something different from the historical BSD implementations can use. > We have lousy functions like gets(3), that we have to keep > because the standards say we do and programmers keep on writing > code that uses them. Complaining about the ability to perform buffer overflows in code that is not SUID/SGID, thereby harming only yourself, is dumb. But... if you are going to keep gets/sprintf/strcpy/etc., just because you think you have to, even though you think they are dumb, then it's probably right to keep historical algorithms intact (technically, buffer overflows in gets() are only possible because the historical algorithm is being kept intact). > rand() and random() have a docimented interface, and empirical > programmer expectations about their outputs simply result in > bad code. Same for use of gets/sprintf/strcpy/etc. for Tuesday's definition of "bad code". I'd argue that providing threads results in bad code, too, but that doesn't mean that they're ging away any time soon. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 04:02:27PM -0800, Juli Mallett wrote: > * De: David Malone <[EMAIL PROTECTED]> [ Data: 2003-02-02 ] > [ Subjecte: Re: rand() is broken ] > > On Sun, Feb 02, 2003 at 02:37:25PM -0800, Steve Kargl wrote: > > > FreeBSD Redhat SunOS > > > 660787754660787754645318364 > > > > FWIW - AIX aggrees with Solaris. > > Endiannes, or an SVR4 implementation difference? The FreeBSD and SunOS man pages are very similar. The FreeBSD man page provides much more detail. Endianness may account for the difference. My OSF/1 box burned its keyboard controller up, so I can't check its random(). -- Steve To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sunday 02 February 2003 11:59 pm, Terry Lambert wrote: > Edward Brocklesby wrote: > > Maybe I missed something, but why cannot you just rip random() from libc, > > rename it to bakul_shah_random() and use that in your testing code? Then > > you are safe from any changes to random(), and indeed have a portable RNG > > if your host OS changes. > > Binary packages from third party software vendors. What about them? They either, a) link to a static libc, and use its rand() always; or b) link to a shared libc, and use its rand(), as the binary API hasn't changed; or c) if they really need their own specific RNG, they include it themselves, and don't rely on libc at all. So I fail to see the problem here. Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Mark Murray <[EMAIL PROTECTED]> wrote: > >3) int random(void) which returns a number statistically > random in all bits. > >We have most of this, and RC4 can deliver. RC4's "licence" is >fine. Call it "ArCFour" and there is no problem. The code is >small, fast and repeatable, and meets conditions 1-4 above. Note that POSIX 2001 states that random() uses a non-linear additive feedback random-number generator, and strongly implies that rand() uses the traditional brain-dead algorithm. Tony. -- f.a.n.finch <[EMAIL PROTECTED]> http://dotat.at/ SOLE LUNDY FASTNET: WEST VEERING NORTHWEST 6 OR 7, OCCASIONALLY GALE 8. RAIN OR SQUALLY SHOWERS. MODERATE OR GOOD. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
* De: David Malone <[EMAIL PROTECTED]> [ Data: 2003-02-02 ] [ Subjecte: Re: rand() is broken ] > On Sun, Feb 02, 2003 at 02:37:25PM -0800, Steve Kargl wrote: > > FreeBSD Redhat SunOS > > 660787754660787754645318364 > > FWIW - AIX aggrees with Solaris. Endiannes, or an SVR4 implementation difference? -- Juli Mallett <[EMAIL PROTECTED]> AIM: BSDFlata -- IRC: juli on EFnet OpenDarwin, Mono, FreeBSD Developer ircd-hybrid Developer, EFnet addict FreeBSD on MIPS-Anything on FreeBSD To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Edward Brocklesby wrote: > On Sunday 02 February 2003 6:48 pm, Bakul Shah wrote: > > Guys, please realize that random() is also used in generating > > simulation inputs (or timing or whatever). If you go change > > the underlying algorithm or its parameters one can't generate > > the same sequence from the same seed when repeating a test. > > Maybe I missed something, but why cannot you just rip random() from libc, > rename it to bakul_shah_random() and use that in your testing code? Then you > are safe from any changes to random(), and indeed have a portable RNG if your > host OS changes. Binary packages from third party software vendors. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Mark Murray wrote: > "Andrey A. Chernov" writes: > > > Objections? > > > > We can't, simple because sequence must be repeated for the same seed > > across the calls. > > RC4 is repeatable. I tried that, and it didn't repeat the sequence I got when I previously used "rand()"... 8-) 8-). -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Mark Murray wrote: > "Jeroen C. van Gelderen" writes: > > Wouldn't it be a good idea to change the name at the same time? Or > > should it be retained for compatibility reasons with other BSDs? > > > > Currently the name needlessly exposes implementation detail. Callers > > expect good, cheap, non-blocking randomness but don't give a hoot if > > that is actually provided trough use of RC4 or not. I see no reason why > > the implementation could be changed if the contract is maintained. > > Good point. We can re-implement random() internally with arc4rand(). > > Objections? The same objections I always raise when someone replaces a PRNG that allows repeatable results with old software with a new one, that does not, I guess. BTW: if /dev/random is so damn good, why are you using it as an implementation detail for these functions, instead of adding yet another backward-incompatible algorithm? -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
[From address modified because I don't want every message in this thread to end up in my personal mailbox. I'll read them in the list, thank you very much.] On Sun, Feb 02, 2003 at 09:23:43PM +, Mark Murray wrote: > Bakul Shah writes: > > > Since you keep talking about random(), I must conclude you're > > > knee-jerking, since we're not discussing that function. Please stay > > > on-topic :-) > > > > Read through the thread. In particular see Mark's message > > <[EMAIL PROTECTED]> where he > > says > > > > Good point. We can re-implement random() internally with arc4rand(). > > Quote it in context, please. > > That was random(9). KERNEL random(). > > However, the argument applies equally well to rand(3) and random(3). Please Mark, just leave rand(3) and random(3) alone -- other than to fix the single bug Kris reported at the start of this thread. Long-time Unix users expect them to work as they do now. The manpages state they are not cryptographically random. If someone wants a function of that type we have a good arc4random(3). To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> Last 10 digits. > > FreeBSD Redhat SunOS > 660787754660787754645318364 > 3275486913275486911583150371 > 2009993994 2009993994 715222008 > 1653966416 1653966416 1349166998 > 1074113008 1074113008 566227131 > 2142626740 2142626740 1382825076 > 1517775852 1517775852 583981903 > 1453318125 1453318125 1453942393 > 6196078076196078071952958724 > 1999863931999863931599163286 Interesting The SunOS output exactly matches random(3) behavior from 4.3BSD! In fact random() remained the same for 4.3BSD-Reno, -Tahoe, 4.4BSD-Alpha and Net2. 4.2BSD random() behavior is different from all of the above. There was real bug-fix between 4.2BSD and 4.3BSD. I don't know when the FreeBSD/Redhat change was made or if it broke any statistical properties. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 02:37:25PM -0800, Steve Kargl wrote: > FreeBSD Redhat SunOS > 660787754660787754645318364 FWIW - AIX aggrees with Solaris. David. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
"Andrey A. Chernov" writes: > On Sun, Feb 02, 2003 at 22:35:54 +, Mark Murray wrote: > > > > I stand (somewhat) corrected. The random() code is _nasty_ complexity-wise. > > Its not obvious how it works. > > > > RC4 is 10-20 lines and clean with no magic numbers. > > That's why randomness tests + mathematician to interpretate their results > are needed to compare what we have now in random(3) with RC4. Easy and > understandable code not always mean better results. We can't switch > algorithms blindly, i.e. when their comparative quality remains unknown. Actually, RC4 is well understood (and trusted). LCRNG's are considered less good in comparison with cryptographic techniques. There is too much to go wrong in them (as you have just discovered!) :-) M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Thus spake Bakul Shah <[EMAIL PROTECTED]>: > > As I said, I don't know how big a concern this is. But last time > > it was enough of a concern to make us keep rand() as it was. > > [I know you are talking about rand() but Mark Murray's > earlier email about wanting to re-implement random() really > concerned me so I want to make sure my point gets across] > > Not changing random() was of real concern to me when I was > doing chip simulations. ASIC design verification folks won't > be happy if the rug is pulled out from under them. In > general crypto and simulation needs are different and I don't > trust the crypto guys to look out for the simulation guys! > > I don't care any more if rand() is changed but _please_ leave > random() alone! And it would be nice to indicate *why* in > the source code for the next time this discussion comes up. If you need guaranteed reproducible random numbers that won't change from system to system or across libc versions, you need to roll your own PRNG. A simple linear congruential generator such as the original BSD algorithm might look random enough for your purposes. But I must admit that I was surprised when Andrey Chernov pointed out that rand() had been replaced between -CURRENT and -STABLE; I thought it was simply common knowledge that rand() was broken, and nobody was interested in fixing it. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 22:35:54 +, Mark Murray wrote: > > I stand (somewhat) corrected. The random() code is _nasty_ complexity-wise. > Its not obvious how it works. > > RC4 is 10-20 lines and clean with no magic numbers. That's why randomness tests + mathematician to interpretate their results are needed to compare what we have now in random(3) with RC4. Easy and understandable code not always mean better results. We can't switch algorithms blindly, i.e. when their comparative quality remains unknown. -- 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: rand() is broken
"Andrey A. Chernov" writes: > On Sun, Feb 02, 2003 at 22:19:33 +, Mark Murray wrote: > > > > 1) Implementing random(3) with RC4 is not needed, its algorithm is > > > already equal or better. > > > > Rubbish. :-) RC4's internal state is 256 bytes. In theory, its > > cycle-of-repetition is 2^(8*256) bits. > > This is comparable with random() TYPE4 which internal state is 252 bytes. I stand (somewhat) corrected. The random() code is _nasty_ complexity-wise. Its not obvious how it works. RC4 is 10-20 lines and clean with no magic numbers. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 01:59:25PM -0800, Bakul Shah wrote:
>
> AFAIK all random(3) implementations in various versions of
> Unix come from Earl's original 4.2BSD implementation so in my
> view the _expected_ behavior is to see the _exact_ same
> sequence starting from a given seed. This function is called
> "random()" but it is equivalent to a mathematical function
> which must provide the same sequence for the exact same
> input.
>
I was going to stay out of this, but
#include
#include
int main(void) {
int i;
long x;
x = 100L;
srandom(x);
for (i = 0; i < 1010; i++) {
x = random();
printf("%ld\n", x);
}
return 0;
}
Last 10 digits.
FreeBSD Redhat SunOS
660787754660787754645318364
3275486913275486911583150371
2009993994 2009993994 715222008
1653966416 1653966416 1349166998
1074113008 1074113008 566227131
2142626740 2142626740 1382825076
1517775852 1517775852 583981903
1453318125 1453318125 1453942393
6196078076196078071952958724
1999863931999863931599163286
--
Steve
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 22:19:33 +, Mark Murray wrote: > > 1) Implementing random(3) with RC4 is not needed, its algorithm is > > already equal or better. > > Rubbish. :-) RC4's internal state is 256 bytes. In theory, its > cycle-of-repetition is 2^(8*256) bits. This is comparable with random() TYPE4 which internal state is 252 bytes. -- 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 0 problem (was Re: rand() is broken)
On Sun, Feb 02, 2003 at 14:21:02 -0800, Kris Kennaway wrote: > > If I understand correctly, this still doesn't solve the problem, > because any PRNG sequence that hits the "magic" value will still get > stuck there forever. It was true for the first patch I post which just move problem to another place (this is commonly spreaded method for this PRNG). It is false for the last patch I post which not stuck with any given seed. -- Andrey A. Chernov http://ache.pp.ru/ msg51605/pgp0.pgp Description: PGP signature
Re: rand() is broken
"Andrey A. Chernov" writes: > On Sun, Feb 02, 2003 at 21:23:43 +, Mark Murray wrote: > > > > That was random(9). KERNEL random(). > > KERNEL random() can be easily implemented (better - replaced) with > arc4random(), there is no objections. But... > > 1) Implementing random(3) with RC4 is not needed, its algorithm is > already equal or better. Rubbish. :-) RC4's internal state is 256 bytes. In theory, its cycle-of-repetition is 2^(8*256) bits. The current library PRNGs are quite a bit less than that. > 2) Implementing rand(3) with RC4 can be possible only if seed (i.e. > state) can be stored in single word (due to rand_r()) restrictions. This is true. Sort of. But in this case, things get less easy. Hmm. I need to look at this some more. Thanks! M M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 12:55:40AM +0300, Andrey A. Chernov wrote: > On Sun, Feb 02, 2003 at 13:06:08 -0800, Kris Kennaway wrote: > > On Sun, Feb 02, 2003 at 06:10:49PM +0300, Andrey A. Chernov wrote: > > > So far, this is final variant for 0 problem fixing ready for committing. > > > Any objections? > > > > What tests have you run on this code to ensure it doesn't still have > > strange problems? > > Uhm, I don't understand you well here. Any code can have strange problems, > nobody can be sure. Lets concentrate to this particular problem which I > call 0 problem. 0 seed is illegal by algorithm desing and BSD developers > try to made workaround, but their attempt was unsuccessful with result you > describe. Now successfull attempt comes. It not add any new bugs, because > value 0 simple mapped to another value (which could be any, but I choose > to not touch lower ones), which make generator non-stick at 0 again. If I understand correctly, this still doesn't solve the problem, because any PRNG sequence that hits the "magic" value will still get stuck there forever. Kris msg51603/pgp0.pgp Description: PGP signature
Re: rand() is broken
Bakul Shah writes: > > No. Evil interface change. #ifdef hell while programs try to > > figure out OS differences. > > How so? This or a similar change is upward compatible in > that the existing behavior is left unchanged and it gives you > a way to replace the algorithm. It requies that programmers know about evil localisms. It screws over portability of source code. > The basic issue is just what is the expected and (implicitly) > promised behavior of random(). You believe one implied output. Another programmer believes another. Only way out is to make the routine "honest". > AFAIK all random(3) implementations in various versions of > Unix come from Earl's original 4.2BSD implementation so in my > view the _expected_ behavior is to see the _exact_ same > sequence starting from a given seed. This function is called > "random()" but it is equivalent to a mathematical function > which must provide the same sequence for the exact same > input. Maybe that is the greatgrandfather. The grandchildren speak with different accents now. :-) > You and a number of other people are saying that the exact > sequence is *not* promised so you are free to change the > algortithm as long as the statistical distribution is > uniform. Not quite. Close. You compile program on a machine with a constant argument to srand[om](). Run the more than once, and rand[om]() will give you the same sequence. Another OS, another time, another version of libc, the sequence will again be constant, but different from last time. > Earl chose to name his new implementation random() [even > though clearly he was replacing rand(3)] probably to not > break any existing scripts. In my view any further behavior > change should either use a new name or make an upward > compatible change. You have said that before, and I understand your words. I disagree with them. > Now the question is whether perl uses system provided > random() or rand() or its own since perl is used extensively > in ASIC verification. Different question. Ask the perl developers. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 21:23:43 +, Mark Murray wrote: > > That was random(9). KERNEL random(). KERNEL random() can be easily implemented (better - replaced) with arc4random(), there is no objections. But... 1) Implementing random(3) with RC4 is not needed, its algorithm is already equal or better. 2) Implementing rand(3) with RC4 can be possible only if seed (i.e. state) can be stored in single word (due to rand_r()) restrictions. -- 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: rand() is broken
> > another suggestion: why not fold your algorithm change in > > that function? For example, > > > > initstate(seed, "RC4", 3); > > > > changes the algorithm to RC4. Yes, this is a change in the > > interface but one I am sure most people can live with. > > No. Evil interface change. #ifdef hell while programs try to > figure out OS differences. How so? This or a similar change is upward compatible in that the existing behavior is left unchanged and it gives you a way to replace the algorithm. The basic issue is just what is the expected and (implicitly) promised behavior of random(). AFAIK all random(3) implementations in various versions of Unix come from Earl's original 4.2BSD implementation so in my view the _expected_ behavior is to see the _exact_ same sequence starting from a given seed. This function is called "random()" but it is equivalent to a mathematical function which must provide the same sequence for the exact same input. You and a number of other people are saying that the exact sequence is *not* promised so you are free to change the algortithm as long as the statistical distribution is uniform. Earl chose to name his new implementation random() [even though clearly he was replacing rand(3)] probably to not break any existing scripts. In my view any further behavior change should either use a new name or make an upward compatible change. Now the question is whether perl uses system provided random() or rand() or its own since perl is used extensively in ASIC verification. Any way, this is my last email on this subject since neither one of us is convincing the other. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Sun, Feb 02, 2003 at 13:06:08 -0800, Kris Kennaway wrote: > On Sun, Feb 02, 2003 at 06:10:49PM +0300, Andrey A. Chernov wrote: > > So far, this is final variant for 0 problem fixing ready for committing. > > Any objections? > > What tests have you run on this code to ensure it doesn't still have > strange problems? Uhm, I don't understand you well here. Any code can have strange problems, nobody can be sure. Lets concentrate to this particular problem which I call 0 problem. 0 seed is illegal by algorithm desing and BSD developers try to made workaround, but their attempt was unsuccessful with result you describe. Now successfull attempt comes. It not add any new bugs, because value 0 simple mapped to another value (which could be any, but I choose to not touch lower ones), which make generator non-stick at 0 again. -- Andrey A. Chernov http://ache.pp.ru/ msg51597/pgp0.pgp Description: PGP signature
Re: Final fix for 0 problem (was Re: rand() is broken)
On Sun, Feb 02, 2003 at 13:12:55 -0800, Doug Barton wrote: > > If I had to guess, I'd say that you're eager to fix the mistake you made, > and I suppose that's commendable. However, it's been broken for two years, > it can wait another couple days for a more thorough fix. If you talk about 0 problem, this mistake is not mine, but inherited from BSD developers who made it in the first place in the kernel. -- 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: rand() is broken
Bakul Shah writes: > > Since you keep talking about random(), I must conclude you're > > knee-jerking, since we're not discussing that function. Please stay > > on-topic :-) > > Read through the thread. In particular see Mark's message > <[EMAIL PROTECTED]> where he > says > > Good point. We can re-implement random() internally with arc4rand(). Quote it in context, please. That was random(9). KERNEL random(). However, the argument applies equally well to rand(3) and random(3). M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, 2 Feb 2003, Bakul Shah wrote: > Yes, *I* can do it but I don't work at every place they do > simulation! Well the code is still going to be available in cvs. It's not like we're going to magically make it disappear. :) > If in the extreme you are suggesting that a > portable application shouldn't rely on any OS features, you > are of course right but that kind of makes mockery of any > claims of compatibility. The point of compatibility is to > not break interfaces unless there is a significant benefit. I can think of one significant benefit... I had noticed that my perl script to pick random windowmaker themes (which uses rand()) seemed to be picking the same themes over and over again. Now I know why. :) I had to create a "last seen" list to artificially increase the "randomness." Oh wait, TWO benefits... xscreensaver is having the same problem. Seriously though, I think the (vast?) majority of our userbase expects random (or even pseudo-random) numbers to be, well, random. For a sufficiently naive definition of random anyway. While I can certainly sympathize with your needs here, with all due respect I think it's an edge case, and one that could be handled with a little customization on your part. Even if you didn't want a code solution, you could spool off BIGNUM "random" numbers from whatever source you choose and save them to disk so that you could get 100% repeatability. Your needs have more than one solution, but I don't think that depending on rand[om]() not to be random is a good one. Doug -- If it's moving, encrypt it. If it's not moving, encrypt it till it moves, then encrypt it some more. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sunday 02 February 2003 8:39 pm, Bakul Shah wrote: > What I am suggesting is to leave random() as it is and > guarantee its behavior won't change and add cryto_random() or > whatever, and indicate it *may* change. Where was it indicated that random() wouldn't change? > Note that it is rand() that is broken, not random() as can be > seen by modifying Kris Kennaways' test so I don't see why > Mark Murray was talking about changing it in the first place. rand()/random() -- either way, the same thing applies, it just happens you use random() rather than rand(). (I see no problem to changing either; do you object to this rand() change on the same basis?) Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Sun, 2 Feb 2003, Andrey A. Chernov wrote: > So far, this is final variant for 0 problem fixing ready for committing. > Any objections? Several people, including myself have asked for A) Enough discussion to reach a consensus, and B) Thorough testing of the agreed upon solution. You have allowed us neither in the 17 minutes you waited between posting this patch and committing it. If I had to guess, I'd say that you're eager to fix the mistake you made, and I suppose that's commendable. However, it's been broken for two years, it can wait another couple days for a more thorough fix. Doug -- If it's moving, encrypt it. If it's not moving, encrypt it till it moves, then encrypt it some more. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
Bakul Shah writes: > random(3) also provides an initstate() call which presumably > allows you to change the amount of randomnes. So here is > another suggestion: why not fold your algorithm change in > that function? For example, > > initstate(seed, "RC4", 3); > > changes the algorithm to RC4. Yes, this is a change in the > interface but one I am sure most people can live with. No. Evil interface change. #ifdef hell while programs try to figure out OS differences. If an os provides a function, that function should be as good as possible while not breaking standards. We have lousy functions like gets(3), that we have to keep because the standards say we do and programmers keep on writing code that uses them. rand() and random() have a docimented interface, and empirical programmer expectations about their outputs simply result in bad code. > > > There is an expectation that on subsequent releases of the > > > same OS things continue to work. > > > > Where is that expectation guaranteed? > > Where is that expectation supported? > > This expectation is a reasonable one. Most commerical OSes > do a good job of maintaining compatibility. IRIX certainly > did a pretty good job of it. FreeBSD also does a pretty good > job on the whole. "Reasonable" is an opinion. It is not shared by me. :-) Irix was well known for its bugs. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Sun, Feb 02, 2003 at 06:10:49PM +0300, Andrey A. Chernov wrote: > So far, this is final variant for 0 problem fixing ready for committing. > Any objections? What tests have you run on this code to ensure it doesn't still have strange problems? Kris msg51583/pgp0.pgp Description: PGP signature
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:57:45PM -0800, Bakul Shah wrote: > > Since you keep talking about random(), I must conclude you're > > knee-jerking, since we're not discussing that function. Please stay > > on-topic :-) > > Read through the thread. In particular see Mark's message > <[EMAIL PROTECTED]> where he > says > > Good point. We can re-implement random() internally with arc4rand(). I assume he transposed and meant "rand() internally with arc4random()". Kris msg51582/pgp0.pgp Description: PGP signature
Re: rand() is broken
Bakul Shah writes: > Note that it is rand() that is broken, not random() as can be > seen by modifying Kris Kennaways' test so I don't see why > Mark Murray was talking about changing it in the first place. rand(3) says: STANDARDS The rand() and srand() functions conform to ISO/IEC 9899:1990 (``ISO C89''). rand(3) does not specify an exact algorithm (the man page does, but not the standard). random(3) has no such standardisation. Any code that assumes particular constants is _broken_[1]. If it has been recompiled or if it is dynamically linked against a shared library other than the one it was tested aginst, different results are a _feature_. M [1] no nitpicking on INT_MAX, please. -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> Since you keep talking about random(), I must conclude you're > knee-jerking, since we're not discussing that function. Please stay > on-topic :-) Read through the thread. In particular see Mark's message <[EMAIL PROTECTED]> where he says Good point. We can re-implement random() internally with arc4rand(). To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
> Would you prefer that we defined random() as
>
> int
> random(void)
> {
> static int retval = 0;
>
> return retval++;
> }
No because that would be a change from the exisiting random()
behavior :-)
As I indicated in my earlier email random() is not broken,
srand() is (as corrected by Andrey Chernov) so you won't be
fixing any bugs by changing random(). If you guys had left
the original rand() alone we wouldn't be discussing any of
this
random(3) also provides an initstate() call which presumably
allows you to change the amount of randomnes. So here is
another suggestion: why not fold your algorithm change in
that function? For example,
initstate(seed, "RC4", 3);
changes the algorithm to RC4. Yes, this is a change in the
interface but one I am sure most people can live with.
> > There is an expectation that on subsequent releases of the
> > same OS things continue to work.
>
> Where is that expectation guaranteed?
> Where is that expectation supported?
This expectation is a reasonable one. Most commerical OSes
do a good job of maintaining compatibility. IRIX certainly
did a pretty good job of it. FreeBSD also does a pretty good
job on the whole.
> The two are related topics.
Yes, but not the same.
> Consider the (joking reference to) "elephant-free biology". :-)
The way things are going we will be there pretty soon :-(
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 11:55:25AM -0800, Bakul Shah wrote: > > RC4 is _utterly_ repeatable, given a particular seed/key. > > May be but it is not the same as the current random(). Also, > I know you will want to change it the next time some one > points out a problem with RC4. Since you keep talking about random(), I must conclude you're knee-jerking, since we're not discussing that function. Please stay on-topic :-) Kris msg51577/pgp0.pgp Description: PGP signature
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:06:56PM -0800, Bakul Shah wrote: > > Maybe I missed something, but why cannot you just rip random() from libc, > > rename it to bakul_shah_random() and use that in your testing code? Then you > > are safe from any changes to random(), and indeed have a portable RNG if your > > host OS changes. > > Yes, *I* can do it but I don't work at every place they do > simulation! If in the extreme you are suggesting that a > portable application shouldn't rely on any OS features, you > are of course right but that kind of makes mockery of any > claims of compatibility. The point of compatibility is to > not break interfaces unless there is a significant benefit. If your program depends on the exact algorithm used by random() (or rand() for that matter) to not change between OS updates (not to mention between different systems) then that is a bug in your program. The interface will not change just because a different algorithm is used. The exact sequence of random numbers produced is not a part of the interface but rather an implementation detail that portable programs should not depend on. It might also be worth noting that if a good PRNG is needed then one should not use random() or rand() since on some systems their output is not very random. -- Erik Trulsson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:39:50 -0800, Bakul Shah wrote: > > Note that it is rand() that is broken, not random() as can be > seen by modifying Kris Kennaways' test so I don't see why > Mark Murray was talking about changing it in the first place. About correlation bug: it is srand() which is broken, not rand(). It is common practice for this type of PRNGs to throw out N values after seeding to remove correlation and srand() not follow this. My first patch fix this. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
