yedidya@bimacs.BITNET (Yedidya Israel) (05/12/91)
I am sending this posting in favor of muskat@bimacs.cs.biu.ac.il
(muskat@bimacs.bitnet), please reply directory to him, if you can
help. Thanks.
From muskat Thu May 9 11:50:22 1991
Date: Thu, 9 May 91 11:50:11 +0200
From: muskat (Prof. J. B. Muskat)
Comments: Internet address: bimacs.cs.biu.ac.il. Bitnet address: bimacs.bitnet.
Old internet address (bimacs.biu.ac.il) is available only temporarily.
To: yedidya
Status: R
To whom it may concern:
Recently I used the random generator random() with the default
seed to generate input for sorting programs. While scanning the results,
I noticed two pairs of very close numbers in the output. When I then
reviewed the input, I was disturbed to find that these numbers came from
nearby positions in the input list, in positions 26 and 29, 27 and 30,
respectively. Since I am not an expert in random number generation, I
should appreciate your reaction.
The program, compiled with gcc and run on a VAX,
and the output are appended.
Sincerely,
Joseph B. Muskat
#define N 40
main()
{ int i;
long heap[N+1];
for (i = 1; i <= N; i++)
{ heap[i] = random();
printf("%3d %12ld %10lx\n", i, heap[i], heap[i]);
}
}
1 2078917053 7be9c1bd
2 143302914 88aa102
3 1027100827 3d38509b
4 1953210302 746b9fbe
5 755253631 2d04417f
6 2002600785 775d4351
7 1405390230 53c48d96
8 45248011 2b26e0b
9 1099951567 418fedcf
10 433832350 19dbc19e
11 2018585307 78512adb
12 438263339 1a1f5e2b
13 813528929 307d7761
14 1703199216 6584c1f0
15 618906479 24e3c36f
16 573714703 2232310f
17 766270699 2dac5ceb
18 275680090 106e8b5a
19 1510320440 5a05a938
20 1583583926 5e6392b6
21 1723401032 66b90348
22 1965443329 75264901
23 1098183682 4174f402
24 1636505764 618b18a4
25 980071615 3a6ab4bf
26 1011597961 3c4bc289 <
27 643279273 2657a9a9 <<
28 1315461275 4e68589b
29 1011597962 3c4bc28a <
30 643279275 2657a9ab <<
31 461447352 1b8120b8
32 1438163612 55b8a29c
33 1946862188 740ac26c
34 392880757 176ae275
35 1581466526 5e43439e
36 826479367 31431307
37 198607412 bd68234
38 189236509 b47851d
39 681596504 28a05658
40 1603997642 5f9b0fca
--
| Israel Yedidya, Math & CS Department, Bar-Ilan U, Ramat-Gan, ISRAEL. |
+----------------------------------------------------------------------+
| Internet: yedidya@bimacs.cs.biu.ac.il Bitnet: yedidya@bimacs |
| Uucp: ...!uunet!pucc.princeton.edu!bimacs!yedidya |
\----------------------------------------------------------------------/
\--- If someone proves there is no God, I'll stop being religious ---/
--------------------------------------------------------------------lance@motcsd.csd.mot.com (lance.norskog) (05/14/91)
yedidya@bimacs.BITNET (Yedidya Israel) writes: >To whom it may concern: > Recently I used the random generator random() with the default >seed to generate input for sorting programs. While scanning the results, >I noticed two pairs of very close numbers in the output. When I then >reviewed the input, I was disturbed to find that these numbers came from >nearby positions in the input list, in positions 26 and 29, 27 and 30, >respectively. Since I am not an expert in random number generation, I >should appreciate your reaction. Ha ha ha! The standard Unix distributions have always had buggy random number generators. You're lucky you were printing them out. Most of us learned this one by writing a game or simulation, and then wondering why some things never ever happened. One of the Knuth books has an exhaustive (you will crawl for three days) treatment of good random number generation. Check it out. Check them all out. The Knuth opus is a wellspring of practical software. Lance
lan_csse@netrix.nac.dec.com (CSSE LAN Test Account) (05/24/91)
>yedidya@bimacs.BITNET (Yedidya Israel) writes: >> Recently I used the random generator random() with the default >>seed to generate input for sorting programs. While scanning the results, >>I noticed two pairs of very close numbers in the output. When I then >>reviewed the input, I was disturbed to find that these numbers came from >>nearby positions in the input list, in positions 26 and 29, 27 and 30, >>respectively. Since I am not an expert in random number generation, I >>should appreciate your reaction. In addition to the Knuth books, here is a routine that I've been passing around for some time. You might install it in your libraries in place of the rand() routine; for your own applications, you can just call minrand() directly. There are probably lots more around... - - - - - - - - - - - - C U T - H E R E - - - - - - - - - - - - - - - - - - - /* minseed(s); ** i = minrand(); ** This is the "minimal standard random" routine by Stephen K. Park and Keith ** W. Miller, in "Random number generators: good ones are hard to find", in ** the Oct 1988 CACM (v.31, no.10). The authors make a good case that this ** is the minimally-acceptable pseudorandom-number generator, as it is highly ** random by all common statistical tests, and has a sufficiently long period ** (2 ^ 31 - 2) for almost all applications. They suggest installing in in ** all libraries in place of the (usually deficient) routines supplied by most ** vendors, and to use an alternate routine only if it is KNOWN to be better. ** ** You are encouraged to give this source code to anyone who wants it. There ** is no copyright. It was typed in by John Chambers in C while reading the ** above article, and I don't think the authors will make any claims on the ** code as long as we continue to give them credit. ** ** This version returns a long int in the range [1..2147483646]. ** ** Any int in the range [1..2147483646] may be used as a seed. To get a unique ** sequence, use an initialization like minseed(getpid()) or minseed(time(0L)). ** For a reproducible sequence, ask the user for a seed, and encourage them to ** use something memorable like their Social Security number. Do not use zero, ** as the result will be a sequence of all zeroes. Note that the upper bound ** is 0x7FFFFFFE, which you may find easier to type. ** ** If compiled with -DTEST, a test driver is compiled that performs the check ** they suggest of starting with seed=1, calculating 10,000 random numbers, ** and verifying the resulting seed. I'd suggest running the test program ** via the command: ** time minrand ** and dividing the results by 10,000. This gives you approximately the time ** to make one minrand() call. */ #define A 16807 /* Multiplier */ #define M 2147483647 /* Modulus */ #define Q 127773 /* M / A */ #define R 2836 /* M % A */ static seed = 1; minseed(s) long s; { seed = s; } long minrand() { long lo, hi, test; hi = seed / Q; lo = seed % Q; test = (A * lo) - (R * hi); seed = (test > 0)? test: test + M; return seed; } #ifdef TEST #include <stdio.h> #define testseed 1043618065 /* Seed 10,001 */ main() { int n; for (n=1; n<=10000; n++) minrand(); if (seed == testseed) fprintf(stderr,"The 10,001st seed is correct: %ld.\n",seed); else fprintf(stderr,"The 10,001st seed is incorrect: %ld.\n",seed); exit(seed != testseed); } #endif