lynx-dev
[Top][All Lists]

## 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;
}

```