+ // Flags to enable various performance profiling options.
+ cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.")
+ memProfile := flag.String("memprofile", "", "Filename for saving memory profile output.")
+ suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.")
+
+ // Obtain termination conditions from user.
+ totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
+ flag.Parse()
+ if *totalGenerations < 1 {
+ log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
+ }
+ remainingGenerations := *totalGenerations - 1
+
+ // Setup any CPU performance profiling requested by the user. This will run
+ // throughout program execution.
+ if *cpuProfile != "" {
+ cpuProFile, err := os.Create(*cpuProfile)
+ if err != nil {
+ log.Fatal("ERROR: Unable to open CPU profiling output file:", err)
+ }
+ pprof.StartCPUProfile(cpuProFile)
+ defer pprof.StopCPUProfile()
+ }
+
+ // Build a universe to contain all the surreal numbers we breed.
+ // Seed it by hand with the number zero as generation-0.
+ var universe surrealUniverse
+ universe.nextUniqueID = 0
+ fmt.Println("Seeding generation 0 by hand.")
+ universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0.0, 0, 0})
+
+ // Breed however many generations of numbers were requested by the user and
+ // add them all to the universe.
+ fmt.Printf("Breeding Generation:")
+ for generation := 1; generation <= remainingGenerations; generation++ {
+ // Give the user some idea of overall progress during long jobs.
+ if generation != 1 {
+ fmt.Printf(",")
+ }
+ fmt.Printf(" %d", generation)
+
+ // First generate all possible new numbers in this generation.
+ potentiallyNewNumbers := permuteExistingNumbers(generation, universe)
+ // Attempt to add the new numbers to the universe. Any duplicates will
+ // be weeded out in the attempt.
+ addNumbersToUniverse(potentiallyNewNumbers, &universe)
+ }
+ fmt.Printf(".\n")
+
+ // Setup any memory profiling requested by the user. This will snapshot
+ // the heap only at this point, after all numbers were generated.
+ if *memProfile != "" {
+ memProFile, err := os.Create(*memProfile)
+ if err != nil {
+ log.Fatal("ERROR: Unable to open heap profile output file:", err)
+ }
+ pprof.WriteHeapProfile(memProFile)
+ memProFile.Close()
+ }
+
+ // Print the number line with generation on the horizontal axis and
+ // magnitude on the vertical axis.
+ if !(*suppressOutput) {
+ for i := 0; i < universe.cardinality(); i++ {
+ printlnNumber(universe.numbers[i])
+ }
+ }
+ fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.")
+ fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.")
+}
+
+// =============================================================================
+
+// We will only build permutations with 0 or 1 elements in each of the left and
+// right sets. This covers all the reduced form permutations. Any longer
+// permutations will be similar to one of the reduced forms.
+func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber {
+ // Profiling indicates that most calls to growSlice() and memMove()
+ // originate in this function. Allocating a sufficiently large slice
+ // upfront results in 2x speed improvement and 1/3 reduction in heap usage.
+ numberOfPermutations := ((universe.cardinality() + 1) * (universe.cardinality() + 1)) - 1
+ numbers := make([]surrealNumber, 0, numberOfPermutations)
+
+ // First build permutations with 1 element in each set.
+ for i := 0; i < universe.cardinality(); i++ {
+ for j := 0; j < universe.cardinality(); j++ {
+ var leftSet, rightSet surrealSet
+ leftSet.insert(universe.numbers[i], universe)
+ rightSet.insert(universe.numbers[j], universe)
+ newSurrealNumber := surrealNumber{leftSet, rightSet, 0.0, 0, generation}
+ if isValidSurrealNumber(newSurrealNumber, universe) {
+ numbers = append(numbers, newSurrealNumber)
+ }
+ }
+ }
+ // Now build permutations with one empty set and one 1-element set.
+ for i := 0; i < universe.cardinality(); i++ {
+ var tempSet surrealSet
+ tempSet.insert(universe.numbers[i], universe)
+ newSurrealNumber := surrealNumber{tempSet, surrealSet{}, 0.0, 0, generation}
+ numbers = append(numbers, newSurrealNumber)
+ newSurrealNumber = surrealNumber{surrealSet{}, tempSet, 0.0, 0, generation}
+ numbers = append(numbers, newSurrealNumber)
+ }
+
+ return numbers
+}
+
+// Although a non-reduced-form number is technically valid, for the purposes of
+// this program we're declaring it invalid.
+func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool {
+ // Is the number in reduced form?
+ if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 {
+ return false
+ }
+
+ // Is the number valid per Axiom 2?
+ if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 {
+ for i := 0; i < candidate.leftSet.cardinality(); i++ {
+ for j := 0; j < candidate.leftSet.cardinality(); j++ {
+ // Since candidates are drawn from the universe, this comparison is allowed.
+ if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) {
+ return false
+ }
+ }
+ }
+ }
+
+ return true
+}
+
+func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) {
+ for i := 0; i < len(numbers); i++ {
+ universe.insert(numbers[i])
+ }
+}
+
+// Pretty print a number, indenting to indicate generation.
+func printlnNumber(num surrealNumber) {
+ for i := 0; i < num.generation; i++ {
+ fmt.Printf(".\t\t")
+ }
+ fmt.Printf("%s = ", toBase26(num.identifier))
+ fmt.Printf("<")
+ if num.leftSet.cardinality() == 0 {
+ fmt.Printf("---")
+ } else {
+ fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier))
+ }
+ fmt.Printf("|")
+ if num.rightSet.cardinality() == 0 {
+ fmt.Printf("---")
+ } else {
+ fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier))
+ }
+ fmt.Printf(">")
+ fmt.Printf("\n")
+}
+
+// This function is a total hack, intended only to avoid printing identifiers
+// as actual numbers since we don't want to imply any particular association to
+// specific 'real' numbers yet. Instead, print them with [a-z] as base-26
+// integers.
+func toBase26(num uint) (base26String []byte) {
+ // For alignment reasons, we never print more than three digits. Thus, any
+ // number greater than (26^3)-1 is out of range.
+ if num >= 26*26*26 {
+ base26String = []byte("xxx")
+ } else {
+ var firstByte, secondByte, thirdByte byte
+ thirdByte = byte((num % 26) + uint('a'))
+ num = num / 26
+ secondByte = byte((num % 26) + uint('a'))
+ num = num / 26
+ firstByte = byte((num % 26) + uint('a'))
+ num = num / 26
+ base26String = append(base26String, firstByte)
+ base26String = append(base26String, secondByte)
+ base26String = append(base26String, thirdByte)
+ }
+ return base26String