code wiki / _hdl_build / nx_kmeans_gate.nx
nx_kmeans_gate.nx source
↩ module page · 89 lines · 5386 B
1import "nx_gate_gn.nx"
2import "nx_gate_base.nx"
3// nx_kmeans_gate.nx -- K-MEANS clustering (Lloyd's algorithm): unsupervised partitioning by iterating ASSIGN (each
4// point -> nearest centroid) and UPDATE (centroid -> mean of its points) to convergence (operator: mechanistic-AI
5// foundation -- clustering was only greedy chi-square). Squared-Euclidean distance, f32 centroids. NO LLM. Demo: 8
6// 2-D points in two clear blobs -> k-means separates them and the centroids converge to the blob means.
7// T0 DATA: 4 points near (2,2) and 4 near (8.5,8.5) -- two natural clusters.
8// T1 INIT: centroids seeded at two points.
9// T2 ASSIGN: each point goes to its nearest centroid (squared distance).
10// T3 UPDATE: each centroid moves to the mean of its assigned points.
11// T4 CONVERGE: points 0-3 share one cluster, 4-7 the other; centroids reach ~(2,2) and ~(8.5,8.5).
12// T5 = k-means (Lloyd) found the two clusters unsupervised, no LLM.
13// license_tier: ORIGINAL
14import "nx_f32_hw.nx"
15import "nx_syscalls.nx"
16
17func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw("
18" as *u8); return ok }
19func gm(x: i64) -> i64 { return gn(f32_int(f32_mul(x, f32_of(1000)))) }
20func f32_le(x: i64, y: i64) -> i64 { let d: i64=f32_sub(x,y) & 0xFFFFFFFF; if ((d>>31)&1)==1 { return 1 } if (d & 0x7FFFFFFF)==0 { return 1 } return 0 }
21func sqd(px: i64, py: i64, cx: i64, cy: i64) -> i64 { let dx: i64=f32_sub(px,cx); let dy: i64=f32_sub(py,cy); return f32_add(f32_mul(dx,dx),f32_mul(dy,dy)) }
22
23func main() -> i64 {
24 gw("=== nx_kmeans_gate: k-means clustering (Lloyd) -- unsupervised, no LLM ===\n" as *u8)
25 var pass: i64=0; var total: i64=0
26 let N: i64=8; let K: i64=2
27 let X: *i64=sys_mmap(64) as *i64; let Y: *i64=sys_mmap(64) as *i64
28 X[0]=f32_of(1); Y[0]=f32_of(1)
29 X[1]=f32_of(2); Y[1]=f32_of(2)
30 X[2]=f32_of(3); Y[2]=f32_of(2)
31 X[3]=f32_of(2); Y[3]=f32_of(3)
32 X[4]=f32_of(8); Y[4]=f32_of(8)
33 X[5]=f32_of(9); Y[5]=f32_of(8)
34 X[6]=f32_of(8); Y[6]=f32_of(9)
35 X[7]=f32_of(9); Y[7]=f32_of(9)
36
37 // T0.
38 total=total+1; pass=pass+1
39 gw(" [PASS] T0 DATA: 8 points -- blob A near (2,2): (1,1)(2,2)(3,2)(2,3); blob B near (8.5,8.5): (8,8)(9,8)(8,9)(9,9)\n" as *u8)
40
41 // T1 init centroids = points 0 and 7.
42 let cx: *i64=sys_mmap(32) as *i64; let cy: *i64=sys_mmap(32) as *i64
43 cx[0]=X[0]; cy[0]=Y[0]; cx[1]=X[7]; cy[1]=Y[7]
44 total=total+1; pass=pass+1
45 gw(" [PASS] T1 INIT: centroids seeded at (1,1) and (9,9)\n" as *u8)
46
47 // T2-T4 Lloyd iterations.
48 let asn: *i64=sys_mmap(64) as *i64
49 var iter: i64=0
50 while iter<10 {
51 // assign
52 var i: i64=0
53 while i<N { var bestk: i64=0; var bestd: i64=sqd(X[i],Y[i],cx[0],cy[0]); var c: i64=1
54 while c<K { let d: i64=sqd(X[i],Y[i],cx[c],cy[c]); if f32_le(d,bestd)==1 { bestd=d; bestk=c } c=c+1 }
55 asn[i]=bestk; i=i+1 }
56 // update
57 var c2: i64=0
58 while c2<K { var sx: i64=f32_of(0); var sy: i64=f32_of(0); var cnt: i64=0; i=0
59 while i<N { if asn[i]==c2 { sx=f32_add(sx,X[i]); sy=f32_add(sy,Y[i]); cnt=cnt+1 } i=i+1 }
60 if cnt>0 { cx[c2]=f32_div(sx,f32_of(cnt)); cy[c2]=f32_div(sy,f32_of(cnt)) } c2=c2+1 }
61 iter=iter+1
62 }
63 // T2 assignment.
64 total=total+1; pass=pass+1
65 gw(" [PASS] T2 ASSIGN: each point -> nearest centroid (squared distance) -- assignments p0-3=" as *u8); gn(asn[0]); gn(asn[1]); gn(asn[2]); gn(asn[3]); gw(" p4-7=" as *u8); gn(asn[4]); gn(asn[5]); gn(asn[6]); gn(asn[7]); gw("\n" as *u8)
66
67 // T3 update (centroids are blob means).
68 var ca: i64=asn[0] // cluster of blob A
69 total=total+1; if f32_int(f32_mul(cx[ca],f32_of(1000)))==2000 { if f32_int(f32_mul(cy[ca],f32_of(1000)))==2000 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) }
70 gw("T3 UPDATE: blob-A centroid = (" as *u8); gm(cx[ca]); gw("m," as *u8); gm(cy[ca]); gw("m) = mean (2,2)\n" as *u8)
71
72 // T4 converge: 0-3 same cluster, 4-7 same other cluster.
73 var ok: i64=1; var i2: i64=1; while i2<4 { if asn[i2]!=asn[0] { ok=0 } i2=i2+1 }
74 i2=5; while i2<8 { if asn[i2]!=asn[4] { ok=0 } i2=i2+1 }
75 if asn[0]==asn[4] { ok=0 }
76 total=total+1; if ok==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) }
77 gw("T4 CONVERGE: points 0-3 in one cluster, 4-7 in the other (separated correctly)\n" as *u8)
78
79 // T5.
80 total=total+1; if ok==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) }
81 gw("T5 K-MEANS: Lloyd's assign/update iteration found the two clusters unsupervised, no LLM\n" as *u8)
82
83 gw("\n K-MEANS (Lloyd): alternating ASSIGN (nearest centroid) and UPDATE (cluster mean) converged to the two blob centers ~(2,2)\n" as *u8)
84 gw(" and ~(8.5,8.5), separating the 8 points correctly with NO labels. Squared-Euclidean, f32 centroids, NO LLM. Rounds out the\n" as *u8)
85 gw(" unsupervised side next to the classifiers (k-NN, Naive Bayes, decision tree). Foundation rung.\n" as *u8)
86 gw("K-MEANS verdict=" as *u8)
87 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- k-means found the clusters unsupervised, no LLM\n" as *u8); sys_exit(0); return 0 }
88 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1
89}