[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
lynx-dev chances for dup temp name (was: Options, V.Links, random)
From: |
Klaus Weide |
Subject: |
lynx-dev chances for dup temp name (was: Options, V.Links, random) |
Date: |
Tue, 21 Dec 1999 03:41:14 -0600 (CST) |
On Tue, 21 Dec 1999, Doug Kaufman wrote:
> The error would have been obvious to me a few years ago, without
> anyone having to point it out.
>
> Correct formula for chance of duplicate values (20 from pool of 10000)
>
> 1 - ( 9999! / (9980! * 10E76 * 20!))
You should have trusted your first instinct. :)
I still think your first formula was the right one:
1 - ( 9999! / (9980! * 10E76))
It looked right, but I don't have any references to back that up.
So to confirm a gut feeling, I just made a brute force test program.
Please try it; a few test runs should show that 2% is the right
order of magnitude, so (2% / 20!) cannot be right.
fmt_counter does about the same thing as fmt_tempname in Lynx;
the details (offset of 1? seed value?) shouldn't matter.
But don't start subsequent test runs the same second, or the
sequence will just repeat.
Klaus
------ snip -----
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NSIM 20 /* number of simultaneous "names" */
unsigned fmt_counter (void)
{
static unsigned counter;
if (counter == 0)
srand(time((time_t *)0));
counter = ( 10000.0 * rand() ) / (RAND_MAX + 1.0);
return counter;
}
/* return 1 if at least one duplicate name, 0 if none */
int onerun (int printit)
{
unsigned names[NSIM];
int i,j;
for (i = 0; i < NSIM; i++) {
names[i] = fmt_counter();
for (j = i-1; j >= 0; j--) {
if (names[j] == names[i]) {
if (printit)
printf("j,i=%.2d,%.2d: name=%u\n", j, i, names[j]);
return 1;
}
}
}
return 0;
}
int main (int argc, char** argv)
{
int samples = 100; /* default */
int samples_with_dup = 0;
int i;
if (argc > 1)
samples = atoi(argv[1]);
printf("samples: %d\n", samples);
for (i = 0; i < samples; i++) {
if (onerun(1))
samples_with_dup++;
}
printf("*** samples with dups: %d\n", samples_with_dup);
return 0;
}