lynx-dev chances for dup temp name (was: Options, V.Links, random)

[Klaus Weide]

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