On Thu, 02 Aug 2007 21:04:00 +0200, Army1987 wrote:
On Thu, 02 Aug 2007 09:27:01 -0700, Keith Thompson wrote:
>Martin Ambuhl <ma*****@earthlink.netwrites:
[...]
>>Do not use the '%' operator to reduce the range of random numbers. It
is a gross error, even with a good pseudo-random number generator.
[...]
Is that true? It seems to me that with a sufficiently good PRNG,
using the '%' operator should yield good results (ignoring the bias
introduced if the range is not a factor of RAND_MAX+1). Using '%' is
a bad idea because the lower bits provided by some PRNGs are poor.
I piped a program writing various sizes, up to 256 MB, of the
lowest byte of rand() (i.e.
for (i=0; i < size; i++)
putchar(rand() & 0xFF);
) into ent (http://www.fourmilab.ch/random/), and it didn't find
anything particular (i.e. most times I got that "Chi-squared would
randomly exceed this xx% of times" with xx between 25 and 75; also
the serial correlation coefficient was very close to zero).
(I didn't try that on Windows, I'll try when I have some spare
time.)
With Microsoft Visual Studio 2005 Express:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SIZE /* see below */
int main(void)
{
size_t n = SIZE;
FILE *out = fopen("rnd.dat", "wb");
if (out == NULL) { perror("fopen"); exit(EXIT_FAILURE); }
srand(time(NULL));
while (n--)
putc(rand() & 0xFF, out); /* CHAR_BIT == 8 */
if (fclose(out) != 0) { perror("fclose"); exit(EXIT_FAILURE); }
return 0;
}
Test: SIZE: Chi square: Serial corr. coefficient:
1 256 264.00 (50%) 0.016030
2 256 286.00 (10%) -0.009120
3 256 260.00 (50%) -0.215230
4 64KB 242.59 (50%) 0.001587
5 64KB 246.53 (50%) -0.003934
6 64KB 231.28 (75%) -0.005520
7 16MB 0.00 (99.99%) 0.000011
(All the values occurred exactly 65536 times; other two tests with
this SIZE gave identical results, except for the Monte Carlo value
for Pi.)
With Microsoft Visual Studio 2005 Express: #include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SIZE 256
int main(void)
{
size_t n = SIZE;
FILE *out = fopen("rnd.dat", "wb");
if (out == NULL) { perror("fopen"); exit(EXIT_FAILURE); }
srand(time(NULL));
while (n--)
putc(rand() >7, out); /* CHAR_BIT == 8, RAND_MAX = 0x7fff */
if (fclose(out) != 0) { perror("fclose"); exit(EXIT_FAILURE); }
return 0;
}
Test: SIZE: Chi square: Serial corr. coefficient:
1 256 266.00 (50%) -0.104760
2 256 260.00 (50%) -0.017179
3 256 280.00 (25%) -0.007335
4 64KB 249.76 (50%) -0.003254
5 64KB 251.86 (50%) -0.002133
6 64KB 242.18 (50%) 0.001661
7 16MB 257.22 (50%) 0.000057
8 16MB 255.54 (50%) -0.000184
9 16MB 253.16 (50%) -0.000410
I haven't saved the results anywhere, but with Ubuntu 6.10,
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5),
libc6 version 2.4-1ubuntu12, I recall that there were no obvious
differences between rand() & 0xFF and rand >15 (RAND_MAX is
2147483647 here).
--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)