--EeQfGwPcQSOJBaQU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

> Note also, that the array that stores the results should be as big as
> the range of the result, so while this should work for 20 bit numbers

I had noticed (and changed) the array size...
 
> I just tried the 20 bit generator, and it's down to a 38 call gap
> between identical ids after 39364490 calls.  Obviously(?) the greater
> range is helping here, but it still has the same basic flaw.

Apply the following:

Index: randomid.c
===================================================================
RCS file: /cvsroot/src/lib/libc/gen/randomid.c,v
retrieving revision 1.3
diff -u -p -r1.3 randomid.c
--- randomid.c	2003/09/10 07:20:13	1.3
+++ randomid.c	2003/09/13 16:18:48
@@ -213,7 +213,7 @@ initid(struct randomid_ctx *p)
 	p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
 
 	/* Determine the LCG we use */
-	p->ru_b = arc4random() | 1;
+	p->ru_b = (arc4random() | 1) % p->ru_m;
 	p->ru_a = pmod(p->ru_agen, arc4random() & (~1U), p->ru_m);
 	while (p->ru_b % 3 == 0)
 		p->ru_b += 2;
@@ -302,11 +302,10 @@ randomid(struct randomid_ctx *p)
 
 	for (i = 0; i <= n; i++) {
 		/* Linear Congruential Generator */
-		p->ru_x = (p->ru_a * p->ru_x + p->ru_b) % p->ru_m;
+		p->ru_x = (uint32_t)(((uint64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m);
 	}
 
 	p->ru_counter += i;
 
-	return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 ^ p->ru_x, p->ru_n)) |
-	    p->ru_msb;
+	return (p->ru_seed ^ pmod(p->ru_g, p->ru_x, p->ru_n)) | p->ru_msb;
 }

ru_msb could be killed - just do 'ru_seed ^= 1 << k'

The attached test program will look for repeats in the 32bit output.
However you need a lot of memory - and it isn't 'cache friendly'.
$ rnd_tst -f randomid -i 'randomid_new(20,3600)' -k 17 -h 21

	David

-- 
David Laight: david@l8s.co.uk

--EeQfGwPcQSOJBaQU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="rnd_tst.c"

#include <sys/types.h>
#include <inttypes.h>
#include <stdio.h>
#include <unistd.h>
#include <stddef.h>
#include <string.h>
#include <stdlib.h>
#include <dlfcn.h>

#define SZ (1 << 16)
#define VALID 0x80000000
#define CLASH 0x40000000

int
main(int argc, char **argv)
{
	uint i, jm, size, limit, l;
	uint hsz, mask, hmask;
	uint64_t j, count;
	uint *val, *hash, *clash;
	uint v, ov, h, hv;
	int nclash = 0;
	char *cp;
	uint (*random_func)(void *);
	void *(*random_init)(uint, uint);
	void *arg = NULL;
	void *dlh = dlopen(NULL, 0);

	setlinebuf(stdout);

	random_func = (void *)&rand;
	size = SZ;
	count = 1 << 24;
	limit = ~0;
	hsz = 0;

#define OPTS "h:i:k:l:n:f:"
	while ((i = getopt(argc, argv, OPTS)) != -1) {
		switch (i) {
		case 'l':
			limit = strtoull(optarg, 0, 0);
			break;
		case 'n':
			count = strtoull(optarg, 0, 0);
			break;
		case 'h':
			hsz = 1 << strtoul(optarg, 0, 0);
			break;
		case 'k':
			size = 1 << strtoul(optarg, 0, 0);
			break;
		case 'f':
			random_func = dlsym(dlh, optarg);
			if (random_func == 0)
				errx(1, "%s not defined", optarg);
			break;
		case 'i':
			cp = strchr(optarg, '(');
			if (cp == NULL)
				errx("no '(' in %s", optarg);
			*cp = 0;
			random_init = dlsym(dlh, optarg);
			*cp = '(';
			v = strtoul(cp + 1, &cp, 0);
			h = strtoul(cp + 1, &cp, 0);
			if (random_init == 0)
				err(1, "%s not defined", optarg);
			arg = random_init(v, h);
			break;
		default:
			errx("usage: %s " OPTS, argv[0]);
		}
	}

	if (hsz < size * 4)
		hsz = size * 4;
	mask = size - 1;
	hmask = hsz - 1;

	val = calloc(size, sizeof *val);
	clash = calloc(size, sizeof *clash);
	hash = calloc(hsz, sizeof *hash);
	if (!val || !clash || !hash) {
		free(val);
		free(clash);
		free(hash);
		err(1, "malloc");
	}

	for (j = 0; j < count; j++) {
		jm = j & mask;
		v = random_func(arg);
		h = v & hmask;
		hv = hash[h];
		if (hv & VALID) {
			hash[h] = hv | CLASH;
			ov = val[hv & mask];
			if (ov == v) {
				l = ((uint)j - hv - 1) & mask;
				if (l < limit) {
					printf("match %8x %8x %8"PRIx64 " %d\n",
					    v, hv, j, l);
					limit = l;
				}
			}

			if (hv & CLASH) {
				for (i = 0; i < nclash; i++) {
					if (val[clash[i]] != v)
						continue;
					l = ((uint)j - clash[i] - 1) & mask;
					if (l >= limit)
						continue;
					limit = l;
					printf("match %8x %8x %8"PRIx64 " %d\n",
					    v, clash[i], j, l);
				}
			}
			clash[nclash++] = jm;
		} else
			hash[h] = jm | VALID;

		ov = val[jm];
		val[jm] = v;
		if (j < size)
			continue;
		h = ov & hmask;
		hv = hash[h];
		if (!(hv & VALID))
			err(1, "VALID not set\n");
		if (!(hv & CLASH)) {
			if (hv != (jm | VALID))
				err(1, "Wrong value: ov %6x hash[%2x] %8x\n",
				    ov, h, hv);
			hash[h] = 0;
			continue;
		}
		if ((hv & mask) != jm) {
			for (i = 0; i < nclash; i++) {
				if (clash[i] != jm)
					continue;
				clash[i] = clash[--nclash];
				break;
			}
			continue;
		}
		for (i = 0; ; i++) {
			if (i == nclash) {
				hash[h] = 0;
				break;
			}
			if ((val[clash[i]] & hmask) != h)
				continue;
			hash[h] = clash[i] | VALID | CLASH;
			clash[i] = clash[--nclash];
			break;
		}
	}

	return 0;
}

--EeQfGwPcQSOJBaQU--