Revamping associative arrays

[BCS]

Hello dsimcha,

> 6.  The array of aaA structs can only have the following sizes:
> 
> immutable size_t[] prime_list = [
> 97UL,            389UL,
> 1_543UL,          6_151UL,
> 24_593UL,         98_317UL,
> 393_241UL,      1_572_869UL,
> 6_291_469UL,     25_165_843UL,
> 100_663_319UL,    402_653_189UL,
> 1_610_612_741UL,  4_294_967_291UL,
> //  8_589_934_513UL, 17_179_869_143UL
> ];
> 
> I understand that there is theoretical justification for this, but in
> practice I'd rather have O(N) performance in a few more corner cases
> in exchange for having my AA not be horribly space-inefficient.
> 

Adding more primes to that list should resolve that issue nicely while retaining 
the advantages of using mod-prime in the hashing.

for example:

1       97
2       197
3       397
4       797
5       1597
6       3203
7       6421
8       12853
9       25717
10      51437
11      102877
12      205759
13      411527
14      823117
15      1646237
16      3292489
17      6584983
18      13169977
19      26339969
20      52679969
21      105359939
22      ...

heres some code to generate a list at whatever rate you want:

import std.stdio;
import std.math;

ulong[] primes;


// running time O(intagral(pi(sqrt(x)), dx, 0, n))
void main()
{
	real rate = 2.0;
	uint from = 97;

	int count = 1;
	writef("%s\t%s\n", count, from);


	primes.length = 10_000; // stop somewhere north of 4_294_967_291UL WARNING: 
this might not end correctly

	long prime_n = 0;
	ulong sqrt_n = 0;
	ulong p = 1;

	outer: while(sqrt_n < primes.length - 5)
	{
		p += 2;
		ulong sqrt_p = 1+cast(ulong)sqrt(cast(real)p);
		sqrt_n = 0;

		while(sqrt_n < prime_n && primes[sqrt_n] <= sqrt_p)
			if(p % primes[sqrt_n] == 0)
				continue outer;
			else
				sqrt_n++;

		if(prime_n < primes.length) primes[prime_n] = p;
		prime_n++;
		if(p >= from * rate)
		{
			count++;
			from = p;
			writef("%s\t%s\n", count, from);
		}
	}
}