compress_test.go raw
1 package cayley
2
3 import (
4 "math/rand"
5 "testing"
6 )
7
8 // compressBacktrack removes adjacent inverse generator pairs.
9 func compressBacktrack(gs *GeneratorSet, path []int8) []int8 {
10 inv := make(map[int8]int8)
11 for i := int8(0); i < int8(len(gs.Gens)); i++ {
12 invMat := gs.Gens[i].Inv(gs.P)
13 for j := int8(0); j < int8(len(gs.Gens)); j++ {
14 if gs.Gens[j].Eq(invMat) { inv[i] = j; break }
15 }
16 }
17 stack := make([]int8, 0, len(path))
18 for _, step := range path {
19 if len(stack) > 0 && inv[stack[len(stack)-1]] == step {
20 stack = stack[:len(stack)-1]
21 } else {
22 stack = append(stack, step)
23 }
24 }
25 return stack
26 }
27
28 // compressGreedy optimizes a valid path by greedy step choice.
29 func compressGreedy(gs *GeneratorSet, path []int8, target Mat2) []int8 {
30 pos := ID()
31 result := make([]int8, 0, len(path))
32 remaining := len(path)
33
34 for !pos.Eq(target) && remaining >= 0 {
35 best := int8(-1)
36 bestDist := int64(1<<63 - 1)
37 for i := int8(0); i < int8(len(gs.Gens)); i++ {
38 next := pos.Mul(gs.Gens[i], gs.P)
39 dist := matDist(next, target, gs.P)
40 if dist < bestDist { bestDist = dist; best = i }
41 }
42 if best < 0 { break }
43 next := pos.Mul(gs.Gens[best], gs.P)
44 if next.Eq(pos) { break }
45 result = append(result, best)
46 pos = next
47 remaining--
48 }
49 if pos.Eq(target) { return result }
50 return path // fallback to original
51 }
52
53 func matDist(a, b Mat2, P int64) int64 {
54 da := mod(a.A-b.A, P); db := mod(a.B-b.B, P)
55 dc := mod(a.C-b.C, P); dd := mod(a.D-b.D, P)
56 return int64(da)*int64(da) + int64(db)*int64(db) + int64(dc)*int64(dc) + int64(dd)*int64(dd)
57 }
58
59 // compressWindow BFS-compresses path within windows of size w.
60 func compressWindow(gs *GeneratorSet, path []int8, target Mat2, w int) []int8 {
61 if w <= 1 || len(path) <= w { return path }
62 pos := ID()
63 result := make([]int8, 0, len(path))
64 b := len(gs.Gens)
65
66 for i := 0; i < len(path); {
67 end := i + w
68 if end > len(path) { end = len(path) }
69 endPos := pos
70 for j := i; j < end; j++ { endPos = endPos.Mul(gs.Gens[path[j]], gs.P) }
71
72 best := path[i:end]
73 bestLen := end - i
74
75 // Enumerate all walks ≤w between pos and endPos.
76 type node struct {
77 m Mat2
78 p []int8
79 }
80 queue := []node{{pos, nil}}
81 seen := map[Mat2]bool{pos: true}
82
83 for len(queue) > 0 && len(queue) < 50000 {
84 n := queue[0]; queue = queue[1:]
85 if len(n.p) >= bestLen { continue }
86 for k := 0; k < b; k++ {
87 next := n.m.Mul(gs.Gens[k], gs.P)
88 if next.Eq(endPos) {
89 np := make([]int8, len(n.p)+1)
90 copy(np, n.p); np[len(n.p)] = int8(k)
91 best = np; bestLen = len(np)
92 goto done
93 }
94 if len(n.p)+1 >= bestLen-1 { continue }
95 if !seen[next] {
96 seen[next] = true
97 np := make([]int8, len(n.p)+1)
98 copy(np, n.p); np[len(n.p)] = int8(k)
99 queue = append(queue, node{next, np})
100 }
101 }
102 }
103 done:
104 result = append(result, best...)
105 pos = endPos
106 i = end
107 }
108 if gs.Walk(ID(), result).Eq(target) { return result }
109 return path
110 }
111
112 // --- Tests ---
113
114 func makeLongPath(target Mat2, gb *GenerativeBasis, P int64, rng *rand.Rand) []int8 {
115 euc, err := EuclideanDecomposition(target, P)
116 if err != nil { return nil }
117 return gb.Sign(euc)
118 }
119
120 func TestCompressBacktrack(t *testing.T) {
121 P := int64(31); rng := rand.New(rand.NewSource(42))
122 gs := randomGens(P, 4, rng)
123 gb := BuildGenerativeBasis(gs)
124 if gb == nil { t.Fatal("no basis") }
125 pf := gb.GPF
126
127 var origT, newT int; n := 0
128 for i := 0; i < 50; i++ {
129 target := randomSL2Fast(P, rng)
130 path := makeLongPath(target, gb, P, rng)
131 if path == nil || len(path) > 400 { continue }
132 opt := compressBacktrack(gs, path)
133 if !gs.Walk(ID(), opt).Eq(target) { continue }
134 origT += len(path); newT += len(opt); n++
135 }
136 if n == 0 { t.Log("no samples"); return }
137 o := float64(origT)/float64(n); nn := float64(newT)/float64(n)
138 om := pf.DistStatsMean()
139 t.Logf("BACKTRACK: orig=%.0f new=%.0f opt=%.0f ratio=%.2f red=%.0f%% n=%d",
140 o, nn, om, nn/o, (1-nn/o)*100, n)
141 }
142
143 func TestCompressGreedy(t *testing.T) {
144 P := int64(31); rng := rand.New(rand.NewSource(42))
145 gs := randomGens(P, 4, rng)
146 gb := BuildGenerativeBasis(gs)
147 if gb == nil { t.Fatal("no basis") }
148 pf := gb.GPF
149
150 var origT, newT int; n := 0
151 for i := 0; i < 50; i++ {
152 target := randomSL2Fast(P, rng)
153 path := makeLongPath(target, gb, P, rng)
154 if path == nil || len(path) > 400 { continue }
155 opt := compressGreedy(gs, path, target)
156 if !gs.Walk(ID(), opt).Eq(target) { continue }
157 origT += len(path); newT += len(opt); n++
158 }
159 if n == 0 { t.Log("no samples"); return }
160 o := float64(origT)/float64(n); nn := float64(newT)/float64(n)
161 om := pf.DistStatsMean()
162 t.Logf("GREEDY: orig=%.0f new=%.0f opt=%.0f ratio=%.2f red=%.0f%% n=%d",
163 o, nn, om, nn/o, (1-nn/o)*100, n)
164 }
165
166 func TestCompressWindow(t *testing.T) {
167 P := int64(31); rng := rand.New(rand.NewSource(42))
168 gs := randomGens(P, 4, rng)
169 gb := BuildGenerativeBasis(gs)
170 if gb == nil { t.Fatal("no basis") }
171 pf := gb.GPF
172
173 for _, w := range []int{3, 4, 5} {
174 var origT, newT int; n := 0
175 for i := 0; i < 30; i++ {
176 target := randomSL2Fast(P, rng)
177 path := makeLongPath(target, gb, P, rng)
178 if path == nil || len(path) > 400 { continue }
179 opt := compressWindow(gs, path, target, w)
180 if !gs.Walk(ID(), opt).Eq(target) { continue }
181 origT += len(path); newT += len(opt); n++
182 }
183 if n == 0 { continue }
184 o := float64(origT)/float64(n); nn := float64(newT)/float64(n)
185 om := pf.DistStatsMean()
186 t.Logf("WINDOW w=%d: orig=%.0f new=%.0f opt=%.0f ratio=%.2f red=%.0f%% n=%d",
187 w, o, nn, om, nn/o, (1-nn/o)*100, n)
188 }
189 }
190
191 func TestCompressCompound(t *testing.T) {
192 P := int64(31); rng := rand.New(rand.NewSource(42))
193 gs := randomGens(P, 4, rng)
194 gb := BuildGenerativeBasis(gs)
195 if gb == nil { t.Fatal("no basis") }
196 pf := gb.GPF
197
198 nSamples := 30
199 var origT, btT, grT, winT int; n := 0
200 for i := 0; i < nSamples; i++ {
201 target := randomSL2Fast(P, rng)
202 path := makeLongPath(target, gb, P, rng)
203 if path == nil || len(path) > 400 { continue }
204
205 // Compound: backtrack → greedy → window(4).
206 p1 := compressBacktrack(gs, path)
207 p2 := compressGreedy(gs, p1, target)
208 p3 := compressWindow(gs, p2, target, 4)
209 if !gs.Walk(ID(), p3).Eq(target) { continue }
210
211 origT += len(path); btT += len(p1); grT += len(p2); winT += len(p3); n++
212 }
213 if n == 0 { return }
214 o := float64(origT)/float64(n)
215 t.Logf("COMPOUND P=%d n=%d:", P, n)
216 t.Logf(" original: %.0f", o)
217 t.Logf(" +backtrack: %.0f (%.0f%%)", float64(btT)/float64(n), float64(btT)/float64(origT)*100)
218 t.Logf(" +greedy: %.0f (%.0f%%)", float64(grT)/float64(n), float64(grT)/float64(origT)*100)
219 t.Logf(" +window(4): %.0f (%.0f%%)", float64(winT)/float64(n), float64(winT)/float64(origT)*100)
220 t.Logf(" BFS optimal: %.0f", pf.DistStatsMean())
221 }
222