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