Commit | Line | Data |
---|---|---|
24271b43 AT |
1 | // (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com> |
2 | // See LICENSE.txt file for copyright and license details. | |
3 | ||
4 | package main | |
5 | ||
6 | import ( | |
3c02a58e | 7 | "flag" |
24271b43 | 8 | "fmt" |
3c02a58e | 9 | "log" |
7a986617 AT |
10 | "os" |
11 | "runtime/pprof" | |
c3b48055 | 12 | "sort" |
24271b43 AT |
13 | ) |
14 | ||
3c02a58e AT |
15 | // ============================================================================= |
16 | ||
90f47767 AT |
17 | // This program recognizes four types of numbers: |
18 | // - Surreal symbols, like those generated by Axiom 1. | |
19 | // - Surreal numbers, like those selected by Axiom 2. | |
20 | // - Reduced form numbers, per Definition 7. | |
21 | // - Named form numbers, which are the equivalence classes induced by | |
22 | // Definition 6, represented by the first representative reduced | |
23 | // form number encountered at runtime. | |
24 | // | |
25 | // Although the surrealNumber type can represent any of these four types of | |
26 | // numbers, the surrealUniverse contains only named form numbers. | |
27 | // | |
28 | // All equality tests (e.g. eq, geq, leq) in this program actually test for | |
29 | // similarity per Definition 6. | |
eaa1dbf5 AT |
30 | |
31 | // ============================================================================= | |
32 | ||
3c02a58e | 33 | type surrealUniverse struct { |
90f47767 AT |
34 | // The elements in this slice are stored in order according to Axiom 3. |
35 | // Thus, numbers[0] < numbers[1] < ... < numbers[n]. | |
3c02a58e | 36 | numbers []surrealNumber |
90f47767 | 37 | nextUniqueID uint |
3c02a58e AT |
38 | } |
39 | ||
90f47767 | 40 | func (u *surrealUniverse) getIndex(num surrealNumber) int { |
c3b48055 AT |
41 | // Since getIndex() is only ever called on 'num' which already exists in |
42 | // the universe, we return the result directly, without bothering to | |
43 | // confirm an exact match. | |
44 | // | |
45 | // Also, we can get away with a direct comparison of these floating point | |
46 | // numbers since there will be an exact match, guaranteed since 'num' is | |
47 | // already in the universe. | |
48 | return sort.Search(u.cardinality(), func(i int) bool {return u.numbers[i].value >= num.value}) | |
3c02a58e AT |
49 | } |
50 | ||
51 | func (u *surrealUniverse) cardinality() int { | |
52 | return len(u.numbers) | |
53 | } | |
54 | ||
55 | func (u *surrealUniverse) insert(num surrealNumber) { | |
90f47767 AT |
56 | // Before we can insert a number into the universe, we must first determine |
57 | // if it is newly discovered. We do this by looking at its ancestors, all | |
58 | // guaranteed to be on the number line by construction, finding three | |
59 | // cases: | |
60 | // | |
61 | // 1. There are zero ancestors. | |
62 | // We have rediscovered 0 and can abort the insertion unless creating | |
63 | // a brand new universe. | |
64 | // | |
65 | // 2. There is one ancestor. | |
66 | // If the number extends the number line, it is new, otherwise it will | |
67 | // be similar to a form with two ancestors and should be ignored since | |
68 | // the two ancestor form is a better visual representation. | |
69 | // | |
70 | // 3. There are two ancestors. | |
71 | // The number is only new if both ancestors are side-by-side on the | |
72 | // number line. | |
73 | ||
74 | ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality() | |
75 | switch ancestorCount { | |
76 | case 0: | |
77 | if u.cardinality() == 0 { | |
c3b48055 | 78 | num.value = 0.0 |
90f47767 AT |
79 | num.identifier = u.nextUniqueID |
80 | u.nextUniqueID++ | |
81 | u.numbers = append(u.numbers, num) | |
82 | } | |
83 | case 1: | |
c3b48055 | 84 | if num.leftSet.cardinality() == 1 { |
90f47767 | 85 | index := u.getIndex(num.leftSet.members[0]) |
90f47767 | 86 | if index+1 == u.cardinality() { |
c3b48055 AT |
87 | num.value = u.numbers[u.cardinality()-1].value + 1.0 |
88 | num.identifier = u.nextUniqueID | |
89 | u.nextUniqueID++ | |
90f47767 AT |
90 | u.numbers = append(u.numbers, num) |
91 | } | |
92 | } else { | |
93 | index := u.getIndex(num.rightSet.members[0]) | |
90f47767 | 94 | if index == 0 { |
c3b48055 AT |
95 | num.value = u.numbers[0].value - 1.0 |
96 | num.identifier = u.nextUniqueID | |
97 | u.nextUniqueID++ | |
90f47767 AT |
98 | u.numbers = append(u.numbers[:1], u.numbers...) |
99 | u.numbers[0] = num | |
100 | } | |
101 | } | |
102 | case 2: | |
103 | leftIndex := u.getIndex(num.leftSet.members[0]) | |
104 | rightIndex := u.getIndex(num.rightSet.members[0]) | |
105 | if leftIndex+1 == rightIndex { | |
c3b48055 | 106 | num.value = (num.leftSet.members[0].value + num.rightSet.members[0].value) / 2 |
90f47767 AT |
107 | num.identifier = u.nextUniqueID |
108 | u.nextUniqueID++ | |
109 | u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...) | |
110 | u.numbers[rightIndex] = num | |
111 | } | |
3c02a58e AT |
112 | } |
113 | } | |
114 | ||
90f47767 AT |
115 | // ============================================================================= |
116 | ||
117 | // Note: The following comparison functions apply only to numbers already in | |
118 | // the universe, not to new numbers constructed from the universe. To | |
119 | // determine where a (potentially) new number goes, first insert it into the | |
120 | // universe. | |
121 | ||
122 | // This function implements Axiom 3 and is the root of all other comparisons. | |
123 | func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool { | |
124 | // By construction, no number in this program will ever have more than one | |
125 | // element in its right or left sets, nor will those elements be of a form | |
126 | // other than that 'registered' with the universe. That allows direct | |
127 | // comparisons using the surrealNumber.identifier field via u.getIndex(). | |
128 | ||
129 | // --------------------------------- | |
130 | ||
131 | // First we implement the check "no member of the first number's left set | |
132 | // is greater than or equal to the second number". | |
133 | if numA.leftSet.cardinality() == 1 { | |
134 | if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) { | |
135 | return false | |
136 | } | |
137 | } | |
138 | ||
139 | // Now we implement the check "no member of the second number's right set | |
140 | // is less than or equal to the first number". | |
141 | if numB.rightSet.cardinality() == 1 { | |
142 | if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) { | |
143 | return false | |
3c02a58e AT |
144 | } |
145 | } | |
90f47767 AT |
146 | |
147 | return true | |
3c02a58e AT |
148 | } |
149 | ||
90f47767 AT |
150 | func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool { |
151 | if u.isRelated(numA, numB) && u.isRelated(numB, numA) { | |
eaa1dbf5 | 152 | return true |
eaa1dbf5 | 153 | } |
90f47767 | 154 | return false |
eaa1dbf5 AT |
155 | } |
156 | ||
90f47767 AT |
157 | func (u *surrealUniverse) equal(left, right surrealNumber) bool { |
158 | return u.isSimilar(left, right) | |
159 | } | |
3c02a58e | 160 | |
90f47767 AT |
161 | func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool { |
162 | return u.isRelated(left, right) | |
3c02a58e AT |
163 | } |
164 | ||
90f47767 AT |
165 | func (u *surrealUniverse) lessThan(left, right surrealNumber) bool { |
166 | return u.lessThanOrEqual(left, right) && !u.equal(left, right) | |
3c02a58e AT |
167 | } |
168 | ||
90f47767 AT |
169 | func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool { |
170 | return !u.lessThan(left, right) | |
171 | } | |
172 | ||
173 | func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool { | |
174 | return !u.isRelated(left, right) | |
3c02a58e AT |
175 | } |
176 | ||
177 | // ============================================================================= | |
178 | ||
90f47767 AT |
179 | type surrealNumber struct { |
180 | leftSet surrealSet | |
181 | rightSet surrealSet | |
c3b48055 | 182 | value float64 |
90f47767 AT |
183 | identifier uint |
184 | generation int | |
185 | } | |
186 | ||
3c02a58e AT |
187 | type surrealSet struct { |
188 | members []surrealNumber | |
189 | } | |
190 | ||
90f47767 | 191 | func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool { |
3c02a58e | 192 | for i := 0; i < len(s.members); i++ { |
90f47767 | 193 | if u.equal(num, s.members[i]) { |
3c02a58e AT |
194 | return true |
195 | } | |
196 | } | |
197 | return false | |
198 | } | |
199 | ||
200 | func (s *surrealSet) cardinality() int { | |
201 | return len(s.members) | |
202 | } | |
203 | ||
90f47767 AT |
204 | func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) { |
205 | if !s.isMember(num, u) { | |
3c02a58e AT |
206 | s.members = append(s.members, num) |
207 | } | |
208 | } | |
209 | ||
90f47767 | 210 | func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) { |
3c02a58e | 211 | for i := 0; i < len(s.members); i++ { |
90f47767 | 212 | if u.equal(num, s.members[i]) { |
3c02a58e AT |
213 | s.members[i] = s.members[len(s.members)-1] |
214 | s.members = s.members[:len(s.members)-1] | |
215 | } | |
216 | } | |
217 | } | |
218 | ||
219 | // ============================================================================= | |
220 | ||
24271b43 | 221 | func main() { |
7a986617 AT |
222 | // Flags to enable various performance profiling options. |
223 | cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.") | |
7757890d | 224 | memProfile := flag.String("memprofile", "", "Filename for saving memory profile output.") |
7a986617 AT |
225 | suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.") |
226 | ||
3c02a58e | 227 | // Obtain termination conditions from user. |
90f47767 | 228 | totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.") |
3c02a58e | 229 | flag.Parse() |
90f47767 | 230 | if *totalGenerations < 1 { |
3c02a58e AT |
231 | log.Fatal("ERROR: The argument to '-generations' must be greater than zero.") |
232 | } | |
90f47767 | 233 | remainingGenerations := *totalGenerations - 1 |
3c02a58e | 234 | |
7a986617 AT |
235 | // Setup any CPU performance profiling requested by the user. This will run |
236 | // throughout program execution. | |
237 | if *cpuProfile != "" { | |
238 | cpuProFile, err := os.Create(*cpuProfile) | |
239 | if err != nil { | |
240 | log.Fatal("ERROR: Unable to open CPU profiling output file:", err) | |
241 | } | |
242 | pprof.StartCPUProfile(cpuProFile) | |
243 | defer pprof.StopCPUProfile() | |
244 | } | |
245 | ||
3c02a58e AT |
246 | // Build a universe to contain all the surreal numbers we breed. |
247 | // Seed it by hand with the number zero as generation-0. | |
248 | var universe surrealUniverse | |
90f47767 | 249 | universe.nextUniqueID = 0 |
1c22e97e | 250 | fmt.Println("Seeding generation 0 by hand.") |
c3b48055 | 251 | universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0.0, 0, 0}) |
3c02a58e | 252 | |
90f47767 AT |
253 | // Breed however many generations of numbers were requested by the user and |
254 | // add them all to the universe. | |
1c22e97e | 255 | fmt.Printf("Breeding Generation:") |
90f47767 | 256 | for generation := 1; generation <= remainingGenerations; generation++ { |
7a986617 | 257 | // Give the user some idea of overall progress during long jobs. |
1c22e97e AT |
258 | if generation != 1 { |
259 | fmt.Printf(",") | |
260 | } | |
261 | fmt.Printf(" %d", generation) | |
7a986617 | 262 | |
70e31d9c AT |
263 | // First generate all possible new numbers in this generation. |
264 | potentiallyNewNumbers := permuteExistingNumbers(generation, universe) | |
90f47767 AT |
265 | // Attempt to add the new numbers to the universe. Any duplicates will |
266 | // be weeded out in the attempt. | |
70e31d9c | 267 | addNumbersToUniverse(potentiallyNewNumbers, &universe) |
3c02a58e | 268 | } |
1c22e97e | 269 | fmt.Printf(".\n") |
3c02a58e | 270 | |
7757890d AT |
271 | // Setup any memory profiling requested by the user. This will snapshot |
272 | // the heap only at this point, after all numbers were generated. | |
273 | if *memProfile != "" { | |
274 | memProFile, err := os.Create(*memProfile) | |
275 | if err != nil { | |
276 | log.Fatal("ERROR: Unable to open heap profile output file:", err) | |
277 | } | |
278 | pprof.WriteHeapProfile(memProFile) | |
279 | memProFile.Close() | |
280 | } | |
7a986617 | 281 | |
90f47767 AT |
282 | // Print the number line with generation on the horizontal axis and |
283 | // magnitude on the vertical axis. | |
7a986617 AT |
284 | if !(*suppressOutput) { |
285 | for i := 0; i < universe.cardinality(); i++ { | |
286 | printlnNumber(universe.numbers[i]) | |
287 | } | |
90f47767 AT |
288 | } |
289 | fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.") | |
290 | fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.") | |
24271b43 | 291 | } |
3c02a58e AT |
292 | |
293 | // ============================================================================= | |
eaa1dbf5 AT |
294 | |
295 | // We will only build permutations with 0 or 1 elements in each of the left and | |
296 | // right sets. This covers all the reduced form permutations. Any longer | |
297 | // permutations will be similar to one of the reduced forms. | |
298 | func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber { | |
8be725f2 AT |
299 | // Profiling indicates that most calls to growSlice() and memMove() |
300 | // originate in this function. Allocating a sufficiently large slice | |
301 | // upfront results in 2x speed improvement and 1/3 reduction in heap usage. | |
302 | numberOfPermutations := ((universe.cardinality()+1) * (universe.cardinality()+1)) - 1 | |
303 | numbers := make([]surrealNumber, 0, numberOfPermutations) | |
eaa1dbf5 AT |
304 | |
305 | // First build permutations with 1 element in each set. | |
306 | for i := 0; i < universe.cardinality(); i++ { | |
307 | for j := 0; j < universe.cardinality(); j++ { | |
308 | var leftSet, rightSet surrealSet | |
90f47767 AT |
309 | leftSet.insert(universe.numbers[i], universe) |
310 | rightSet.insert(universe.numbers[j], universe) | |
c3b48055 | 311 | newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,0,generation} |
70e31d9c AT |
312 | if isValidSurrealNumber(newSurrealNumber, universe) { |
313 | numbers = append(numbers, newSurrealNumber) | |
314 | } | |
eaa1dbf5 AT |
315 | } |
316 | } | |
317 | // Now build permutations with one empty set and one 1-element set. | |
318 | for i := 0; i < universe.cardinality(); i++ { | |
319 | var tempSet surrealSet | |
90f47767 | 320 | tempSet.insert(universe.numbers[i], universe) |
c3b48055 | 321 | newSurrealNumber := surrealNumber{tempSet,surrealSet{},0.0,0,generation} |
eaa1dbf5 | 322 | numbers = append(numbers, newSurrealNumber) |
c3b48055 | 323 | newSurrealNumber = surrealNumber{surrealSet{},tempSet,0.0,0,generation} |
eaa1dbf5 AT |
324 | numbers = append(numbers, newSurrealNumber) |
325 | } | |
326 | ||
327 | return numbers | |
328 | } | |
329 | ||
eaa1dbf5 AT |
330 | // Although a non-reduced-form number is technically valid, for the purposes of |
331 | // this program we're declaring it invalid. | |
332 | func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool { | |
90f47767 AT |
333 | // Is the number in reduced form? |
334 | if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 { | |
eaa1dbf5 AT |
335 | return false |
336 | } | |
337 | ||
90f47767 AT |
338 | // Is the number valid per Axiom 2? |
339 | if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 { | |
340 | for i := 0; i < candidate.leftSet.cardinality(); i++ { | |
341 | for j := 0; j < candidate.leftSet.cardinality(); j++ { | |
342 | // Since candidates are drawn from the universe, this comparison is allowed. | |
343 | if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) { | |
344 | return false | |
345 | } | |
346 | } | |
eaa1dbf5 AT |
347 | } |
348 | } | |
349 | ||
350 | return true | |
351 | } | |
352 | ||
353 | func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) { | |
354 | for i := 0; i < len(numbers); i++ { | |
355 | universe.insert(numbers[i]) | |
356 | } | |
357 | } | |
358 | ||
90f47767 AT |
359 | // Pretty print a number, indenting to indicate generation. |
360 | func printlnNumber(num surrealNumber) { | |
361 | for i := 0; i < num.generation; i++ { | |
362 | fmt.Printf(".\t\t") | |
363 | } | |
364 | fmt.Printf("%s = ", toBase26(num.identifier)) | |
365 | fmt.Printf("<") | |
366 | if num.leftSet.cardinality() == 0 { | |
367 | fmt.Printf("---") | |
368 | } else { | |
369 | fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier)) | |
370 | } | |
371 | fmt.Printf("|") | |
372 | if num.rightSet.cardinality() == 0 { | |
373 | fmt.Printf("---") | |
374 | } else { | |
375 | fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier)) | |
376 | } | |
377 | fmt.Printf(">") | |
378 | fmt.Printf("\n") | |
379 | } | |
380 | ||
381 | // This function is a total hack, intended only to avoid printing identifiers | |
382 | // as actual numbers since we don't want to imply any particular association to | |
383 | // specific 'real' numbers yet. Instead, print them with [a-z] as base-26 | |
384 | // integers. | |
385 | func toBase26(num uint) (base26String []byte) { | |
386 | // For alignment reasons, we never print more than three digits. Thus, any | |
387 | // number greater than (26^3)-1 is out of range. | |
388 | if num >= 26*26*26 { | |
389 | base26String = []byte("xxx") | |
390 | } else { | |
391 | var firstByte, secondByte, thirdByte byte | |
392 | thirdByte = byte((num % 26) + uint('a')); | |
393 | num = num / 26; | |
394 | secondByte = byte((num % 26) + uint('a')); | |
395 | num = num / 26; | |
396 | firstByte = byte((num % 26) + uint('a')); | |
397 | num = num / 26; | |
398 | base26String = append(base26String, firstByte) | |
399 | base26String = append(base26String, secondByte) | |
400 | base26String = append(base26String, thirdByte) | |
401 | } | |
402 | return base26String | |
403 | } |