5 // TODO: use large period prng
6 static uint64_t seed = -1;
7 static uint32_t rand32(void)
9 seed = 6364136223846793005ULL*seed + 1;
12 static uint64_t rand64(void)
14 uint64_t u = rand32();
15 return u<<32 | rand32();
19 return rand64() * 0x1p-64;
23 return rand32() * 0x1p-32f;
25 static long double frandl()
27 return rand64() * 0x1p-64L
28 #if LDBL_MANT_DIG > 64
29 + rand64() * 0x1p-128L
34 void t_randseed(uint64_t s)
39 /* uniform random in [0,n), n > 0 must hold */
40 uint64_t t_randn(uint64_t n)
44 /* m is the largest multiple of n */
47 while ((r = rand64()) >= m);
51 /* uniform on [a,b], a <= b must hold */
52 uint64_t t_randint(uint64_t a, uint64_t b)
54 uint64_t n = b - a + 1;
56 return a + t_randn(n);
60 /* shuffle the elements of p and q until the elements in p are well shuffled */
61 static void shuffle2(uint64_t *p, uint64_t *q, size_t np, size_t nq)
79 /* shuffle the elements of p */
80 void t_shuffle(uint64_t *p, size_t n)
85 void t_randrange(uint64_t *p, size_t n)
88 for (i = 0; i < n; i++)
93 /* hash table insert, 0 means empty, v > 0 must hold, len is power-of-2 */
94 static int insert(uint64_t *tab, size_t len, uint64_t v)
96 size_t i = v & (len-1);
109 /* choose k unique numbers from [0,n), k <= n */
110 int t_choose(uint64_t n, size_t k, uint64_t *p)
121 if (t_randn(n--) < k)
127 /* no alloc, n > 15 > 2*k */
128 for (i = 0; i < k;) {
130 for (j = 0; p[j] != p[i]; j++);
137 // TODO: if k < n/k use k*log(k) solution without alloc
139 if (n < 5*k && (n-k)*sizeof *tab < (size_t)-1) {
140 /* allocation is n-k < 4*k */
141 tab = malloc((n-k) * sizeof *tab);
144 for (i = 0; i < k; i++)
149 shuffle2(p, tab, k, n-k);
151 shuffle2(tab, p, n-k, k);
156 /* allocation is 2*k <= len < 4*k */
157 for (len = 16; len < 2*k; len *= 2);
158 tab = calloc(len, sizeof *tab);
161 for (i = 0; i < k; i++)
162 while (insert(tab, len, t_randn(n)+1));
163 for (i = 0; i < len; i++)