Re: rand() is broken

2003-02-05 Thread Narvi
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

Re: rand() is broken

2003-02-05 Thread Narvi
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

Re: rand() is broken

2003-02-05 Thread Narvi
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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... --

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread David Schultz
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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):

Re: rand() is broken

2003-02-04 Thread Dag-Erling Smorgrav
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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):

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Dag-Erling Smorgrav
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Dag-Erling Smorgrav
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Dag-Erling Smorgrav
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

Re: rand() is broken

2003-02-04 Thread Dag-Erling Smorgrav
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()

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-04 Thread Andrey A. Chernov
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:

Re: rand() is broken

2003-02-03 Thread David Malone
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

Re: rand() is broken

2003-02-03 Thread Juli Mallett
* 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

Re: rand() is broken

2003-02-03 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-03 Thread Brad Knowles
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

Re: rand() is broken

2003-02-03 Thread Alexander Pohoyda
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: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Mark Murray
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

Re: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Re: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Re: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Mark Murray
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

Re: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Re: Final fix for 0 problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Final fix for correlation problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Re: Final fix for correlation problem (was Re: rand() is broken)

2003-02-03 Thread Thomas David Rivers
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

Re: Final fix for correlation problem (was Re: rand() is broken)

2003-02-03 Thread Andrey A. Chernov
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

Re: Final fix for correlation problem (was Re: rand() is broken)

2003-02-03 Thread Erik Trulsson
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

Re: Final fix for correlation problem (was Re: rand() is broken)

2003-02-03 Thread David Schultz
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

Re: rand() is broken

2003-02-03 Thread Dag-Erling Smorgrav
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

Re: rand() is broken

2003-02-03 Thread Terry Lambert
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

Re: rand() is broken

2003-02-03 Thread David Schultz
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

Re: rand() is broken

2003-02-03 Thread Eric Hodel
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

Re: rand() is broken

2003-02-03 Thread David Schultz
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()

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-02 Thread Kris Kennaway
On Sun, Feb 02, 2003 at 12:04:22PM +0300, Andrey A. Chernov wrote: 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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). It looks like a lot more validation of

Re: rand() is broken

2003-02-02 Thread phk
In message [EMAIL PROTECTED], Andrey A. Chernov writes: --SUOF0GtieIMvvwua Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: =20 Another problem (noticed by tjr) is that

Re: rand() is broken

2003-02-02 Thread Mark Murray
[EMAIL PROTECTED] writes: BTW, note that new formulae also used in the kernel (by BSD developers) and taken from there - libkern/random.c - so all you say is true there too. It should be nuked from the kernel, and arc4random() used instead. I agree. If no-one objects, I'll do this? M --

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). It looks like a lot more validation of

Re: rand() is broken

2003-02-02 Thread David Schultz
Thus spake Andrey A. Chernov [EMAIL PROTECTED]: 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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 03:48:17 -0800, David Schultz wrote: Specifically, rand() isn't very interesting in the lower-order bits, and it spectacularly fails nearly all of Marsaglia's It seems that you speak about old formulae, we use new one (which intended to fix low-ordered bits), see our

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote: Workaround I find so far is something like that #define MASK 123459876 I found nothing better. Here is fix for 0 problem I plan to commit: --- stdlib/rand.c.old Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2

Re: rand() is broken

2003-02-02 Thread Doug Barton
On Sun, 2 Feb 2003, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote: Workaround I find so far is something like that #define MASK 123459876 I found nothing better. Here is fix for 0 problem I plan to commit: I think it's worthwhile to wait till

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 04:38:53 -0800, Doug Barton wrote: I think it's worthwhile to wait till we get a chance to try arc4random(). This is libc's rand/random, it can't be fixed with arc4random() as designed. Also, have you run the code you're proposing through the tests in the post that

Re: rand() is broken

2003-02-02 Thread Tim Robbins
On Sun, Feb 02, 2003 at 03:30:35PM +0300, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote: Workaround I find so far is something like that #define MASK 123459876 I found nothing better. Here is fix for 0 problem I plan to commit: ---

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is possible for this formulae and this is documented in algorithm, some value

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 16:42:25 +0300, Andrey A. Chernov wrote: On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 17:02:23 +0300, Andrey A. Chernov wrote: I'll produce and send it a bit later. Here it is. --- stdlib/rand.c.old Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2 17:06:08 2003 @@ -72,10 +72,13 @@ */ long hi, lo, x; + /* Can't be

Final fix for 0 problem (was Re: rand() is broken)

2003-02-02 Thread Andrey A. Chernov
So far, this is final variant for 0 problem fixing ready for committing. Any objections? --- stdlib/rand.c.old Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2 17:34:34 2003 @@ -72,10 +72,13 @@ */ long hi, lo, x; + /* Can't be initialized with 0, so use another

Re: rand() is broken

2003-02-02 Thread Dag-Erling Smorgrav
David Schultz [EMAIL PROTECTED] writes: [2] http://stat.fsu.edu/~geo/diehard.html (you need ports/lang/f2c) There's a native C version on Marsaglia's random number CD: http://stat.fsu.edu/pub/diehard/cdrom/die.c/ DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to

Re: rand() is broken

2003-02-02 Thread Mark Murray
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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 15:32:32 +, 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.

Re: rand() is broken

2003-02-02 Thread Mark Murray
Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 04:38:53 -0800, Doug Barton wrote: I think it's worthwhile to wait till we get a chance to try arc4random(). This is libc's rand/random, it can't be fixed with arc4random() as designed. Why not? Arc4 is a) deterministic and b) good for

Re: rand() is broken

2003-02-02 Thread Mark Murray
Andrey A. Chernov writes: On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is possible for this formulae and this is

Re: rand() is broken

2003-02-02 Thread Mark Murray
Andrey A. Chernov writes: Objections? We can't, simple because sequence must be repeated for the same seed across the calls. RC4 is repeatable. 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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 17:34:19 +, 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. It seems we mean different things saying arc4random(), see my answer in the

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 21:20:09 +0300, 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,

Re: rand() is broken

2003-02-02 Thread phk
In message [EMAIL PROTECTED], Andrey A. Chernov writes: 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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-02 Thread Mark Murray
Andrey A. Chernov writes: 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

Re: rand() is broken

2003-02-02 Thread phk
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

Re: rand() is broken

2003-02-02 Thread phk
In message [EMAIL PROTECTED], Mark Murray wr ites: 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. There are some concerns about RC4's strength and predictability.

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 19:43:44 +0100, [EMAIL PROTECTED] wrote: 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(). I remember well that we decide to allow it be changed

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 19:47:12 +0100, [EMAIL PROTECTED] wrote: In message [EMAIL PROTECTED], Mark Murray wr ites: 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

Re: rand() is broken

2003-02-02 Thread Mark Murray
[EMAIL PROTECTED] writes: In message [EMAIL PROTECTED], Mark Murray wr ites: 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. There are some concerns about

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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

Re: rand() is broken

2003-02-02 Thread Mark Murray
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. RC4 is _utterly_ repeatable, given a particular seed/key. The old 16 bit rand() was broken enough

Re: rand() is broken

2003-02-02 Thread Mark Murray
Bakul Shah writes: 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

Re: rand() is broken

2003-02-02 Thread David Malone
On Sun, Feb 02, 2003 at 07:08:47PM +, Mark Murray wrote: RC4 is _utterly_ repeatable, given a particular seed/key. I presume it also produces reasonably uniform output for most seeds too. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its

Re: rand() is broken

2003-02-02 Thread Edward Brocklesby
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

Re: rand() is broken

2003-02-02 Thread Mark Murray
. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has a pretty long cycle and enough randomness to be very useful and it *is* used. Yes. And it breaks, and we have a complainant. I thought the complaint

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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. Yes. And it breaks, and we have a complainant. So create a new function! Or use a

Re: rand() is broken

2003-02-02 Thread David Malone
I presume it also produces reasonably uniform output for most seeds too. Yes. Modulo the requirement to burn a bit of output after a reseed. I guess the crypto guys would have junked it otherwise ;-) I thought the complaint was about rand, not random? Erm, yes. Similar difference

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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

Re: rand() is broken

2003-02-02 Thread Edward Brocklesby
On Sunday 02 February 2003 8:06 pm, 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

Re: rand() is broken

2003-02-02 Thread Mark Murray
Bakul Shah writes: 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. Yes. This is called fixing bugs. We (OS maintainers) reserve

Re: rand() is broken

2003-02-02 Thread Mark Murray
Bakul Shah writes: 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

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
On Sun, Feb 02, 2003 at 20:05:29 +, David Malone wrote: I presume it also produces reasonably uniform output for most seeds too. Yes. Modulo the requirement to burn a bit of output after a reseed. I guess the crypto guys would have junked it otherwise ;-) Notice that it will

Re: rand() is broken

2003-02-02 Thread Bakul Shah
. 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. #include stdlib.h #include stdio.h int main() { int i; for(i = 1; i = 1000; i

Re: rand() is broken

2003-02-02 Thread Andrey A. Chernov
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

Re: rand() is broken

2003-02-02 Thread Erik Trulsson
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

Re: rand() is broken

2003-02-02 Thread Kris Kennaway
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

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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

Re: rand() is broken

2003-02-02 Thread Bakul Shah
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

Re: rand() is broken

2003-02-02 Thread Mark Murray
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

Re: rand() is broken

2003-02-02 Thread Kris Kennaway
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

  1   2   >