X-Git-Url: http://git.subgeniuskitty.com/surreal-numbers/.git/blobdiff_plain/eaa1dbf5d3a89a2276ec7ac84db03ab61e8a9a70..213fa8b5b4ce7a2531f07197927b3b4c06a2714b:/chapter-1-experiments/ch1-breeding-numbers.go

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index b990361..a2b8d34 100644
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -4,195 +4,290 @@
 package main
 
 import (
-    "flag"
-    "fmt"
-    "log"
+	"flag"
+	"fmt"
+	"log"
+	"os"
+	"runtime/pprof"
+	"sort"
 )
 
 // =============================================================================
 
-// TODO: Anywhere we do simple comparisons for number equality testing, we need
-// to upgrade to dual-LEQ comparisons.
+// This program recognizes four types of numbers:
+//   - Surreal symbols, like those generated by Axiom 1.
+//   - Surreal numbers, like those selected by Axiom 2.
+//   - Reduced form numbers, per Definition 7.
+//   - Named form numbers, which are the equivalence classes induced by
+//         Definition 6, represented by the first representative reduced
+//         form number encountered at runtime.
+//
+// Although the surrealNumber type can represent any of these four types of
+// numbers, the surrealUniverse contains only named form numbers.
+//
+// All equality tests (e.g. eq, geq, leq) in this program actually test for
+// similarity per Definition 6.
 
 // =============================================================================
 
 type surrealUniverse struct {
-    // TODO: Note that the elements of this array are maintained in order
-    // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine?
-    numbers []surrealNumber
-    nextUniqueID int
+	// The elements in this slice are stored in order according to Axiom 3.
+	// Thus, numbers[0] < numbers[1] < ... < numbers[n].
+	numbers      []surrealNumber
+	nextUniqueID uint
 }
 
-func (u *surrealUniverse) getIndex(num surrealNumber) (exists bool, index int) {
-    // TODO: After I implement a LEQ comparison function, the fact that
-    // u.numbers[] is ordered by that comparison will allow me to greatly
-    // shorten the search.
-    for i := 0; i < len(u.numbers); i++ {
-        if num.number == u.numbers[i].number {
-            return true, i
-        }
-    }
-    return false, 0
+func (u *surrealUniverse) getIndex(num surrealNumber) int {
+	// Since getIndex() is only ever called on 'num' which already exists in
+	// the universe, we return the result directly, without bothering to
+	// confirm an exact match.
+	//
+	// Also, we can get away with a direct comparison of these floating point
+	// numbers since there will be an exact match, guaranteed since 'num' is
+	// already in the universe.
+	return sort.Search(u.cardinality(), func(i int) bool { return u.numbers[i].value >= num.value })
 }
 
 func (u *surrealUniverse) cardinality() int {
-    return len(u.numbers)
+	return len(u.numbers)
 }
 
 func (u *surrealUniverse) insert(num surrealNumber) {
-    exists, _ := u.getIndex(num)
-    if !exists {
-        num.metadata.identifier = u.nextUniqueID
-        u.nextUniqueID++
-        // Find spot to insert based on ordering defined in Axiom 2.
-        // TODO: Insert some comments explaining the basic algorithm.
-        for i := 0; i < len(u.numbers); i++ {
-
-//            if num.number.leftSet != nil {
-//                // By assumption, everything is in reduced form by this point,
-//                // thus there is precisely one element at this time.
-//                _, leftIndex := u.getIndex(num.number.leftSet[0])
-//                _, rightIndex := u.getIndex(u.numbers[i])
-//                if leftIndex >= rightIndex {
-//                    // num is NOT LEQ to u.numbers[i]
-//                }
-//            }
-//            if u.numbers[i].rightSet != nil {
-//                // TODO: How do I check if the second number's rightSet is less
-//                // than or equal to the first number? After all, the first
-//                // number isn't on the numberline yet.
-//            }
-
-// =================================================================================================
-//// Algorithm
-//foreach u.numbers as oldNum, in increasing order:
-//    if newNum <= oldNum:
-//        if oldNum <= newNum:
-//            // the number are the same, just in a different reduced form.
-//        else:
-//            // Insert newNum immediately before oldNum
-//    else:
-//        if more oldNums exist:
-//            // loop and try the next oldNum
-//        else:
-//            // Found a new largest number?
-// =================================================================================================
-
-//            if !lessThanOrEqual(num, u.numbers[i]) {
-//                if i+1 < len(u.numbers) {
-//                    // There are still more entries to check.
-//                    continue
-//                } else {
-//                    // New largest number. Append to numberline.
-//                    u.numbers = append(u.numbers, num)
-//                }
-//            } else {
-//                // Found insertion spot between two existing numbers.
-//                u.numbers = append(u.numbers[:i], num, u.numbers[i:]...)
-//            }
-        }
-    }
+	// Before we can insert a number into the universe, we must first determine
+	// if it is newly discovered. We do this by looking at its ancestors, all
+	// guaranteed to be on the number line by construction, finding three
+	// cases:
+	//
+	//   1. There are zero ancestors.
+	//      We have rediscovered 0 and can abort the insertion unless creating
+	//      a brand new universe.
+	//
+	//   2. There is one ancestor.
+	//      If the number extends the number line, it is new, otherwise it will
+	//      be similar to a form with two ancestors and should be ignored since
+	//      the two ancestor form is a better visual representation.
+	//
+	//   3. There are two ancestors.
+	//      The number is only new if both ancestors are side-by-side on the
+	//      number line.
+
+	ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality()
+	switch ancestorCount {
+	case 0:
+		if u.cardinality() == 0 {
+			num.value = 0.0
+			num.identifier = u.nextUniqueID
+			u.nextUniqueID++
+			u.numbers = append(u.numbers, num)
+		}
+	case 1:
+		if num.leftSet.cardinality() == 1 {
+			index := u.getIndex(num.leftSet.members[0])
+			if index+1 == u.cardinality() {
+				num.value = u.numbers[u.cardinality()-1].value + 1.0
+				num.identifier = u.nextUniqueID
+				u.nextUniqueID++
+				u.numbers = append(u.numbers, num)
+			}
+		} else {
+			index := u.getIndex(num.rightSet.members[0])
+			if index == 0 {
+				num.value = u.numbers[0].value - 1.0
+				num.identifier = u.nextUniqueID
+				u.nextUniqueID++
+				u.numbers = append(u.numbers[:1], u.numbers...)
+				u.numbers[0] = num
+			}
+		}
+	case 2:
+		leftIndex := u.getIndex(num.leftSet.members[0])
+		rightIndex := u.getIndex(num.rightSet.members[0])
+		if leftIndex+1 == rightIndex {
+			num.value = (num.leftSet.members[0].value + num.rightSet.members[0].value) / 2
+			num.identifier = u.nextUniqueID
+			u.nextUniqueID++
+			u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)
+			u.numbers[rightIndex] = num
+		}
+	}
 }
 
-func (u *surrealUniverse) remove(num surrealNumber) {
-    for i := 0; i < len(u.numbers); i++ {
-        if num.number == u.numbers[i].number {
-            u.numbers = append(u.numbers[:i], u.numbers[i+1:]...)
-        }
-    }
+// =============================================================================
+
+// Note: The following comparison functions apply only to numbers already in
+// the universe, not to new numbers constructed from the universe.  To
+// determine where a (potentially) new number goes, first insert it into the
+// universe.
+
+// This function implements Axiom 3 and is the root of all other comparisons.
+func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool {
+	// By construction, no number in this program will ever have more than one
+	// element in its right or left sets, nor will those elements be of a form
+	// other than that 'registered' with the universe. That allows direct
+	// comparisons using the surrealNumber.identifier field via u.getIndex().
+
+	// ---------------------------------
+
+	// First we implement the check "no member of the first number's left set
+	// is greater than or equal to the second number".
+	if numA.leftSet.cardinality() == 1 {
+		if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) {
+			return false
+		}
+	}
+
+	// Now we implement the check "no member of the second number's right set
+	// is less than or equal to the first number".
+	if numB.rightSet.cardinality() == 1 {
+		if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) {
+			return false
+		}
+	}
+
+	return true
 }
 
-// TODO: Note that this is only for numbers already in the universe, not for
-// new numbers constructed FROM the universe.  To determine where a new number
-// goes, insert it into the universe.
-func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
-    _, leftIndex := u.getIndex(left)
-    _, rightIndex := u.getIndex(right)
-    if leftIndex <= rightIndex {
-        return true
-    } else {
-        return false
-    }
+func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool {
+	if u.isRelated(numA, numB) && u.isRelated(numB, numA) {
+		return true
+	}
+	return false
 }
 
-// =============================================================================
+func (u *surrealUniverse) equal(left, right surrealNumber) bool {
+	return u.isSimilar(left, right)
+}
 
-type surrealNumber struct {
-    number surrealValue
-    metadata surrealMetadata
+func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
+	return u.isRelated(left, right)
+}
+
+func (u *surrealUniverse) lessThan(left, right surrealNumber) bool {
+	return u.lessThanOrEqual(left, right) && !u.equal(left, right)
 }
 
-// TODO: Note that this is split from the metadata so we can do direct
-// comparisons when numbers are in reduced form.
-type surrealValue struct {
-    leftSet *surrealSet
-    rightSet *surrealSet
+func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool {
+	return !u.lessThan(left, right)
 }
 
-type surrealMetadata struct {
-    identifier int
-    generation int
+func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
+	return !u.isRelated(left, right)
 }
 
 // =============================================================================
 
+type surrealNumber struct {
+	leftSet    surrealSet
+	rightSet   surrealSet
+	value      float64
+	identifier uint
+	generation int
+}
+
 type surrealSet struct {
-    members []surrealNumber
+	members []surrealNumber
 }
 
-func (s *surrealSet) isMember(num surrealNumber) bool {
-    for i := 0; i < len(s.members); i++ {
-        if num.number == s.members[i].number {
-            return true
-        }
-    }
-    return false
+func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool {
+	for i := 0; i < len(s.members); i++ {
+		if u.equal(num, s.members[i]) {
+			return true
+		}
+	}
+	return false
 }
 
 func (s *surrealSet) cardinality() int {
-    return len(s.members)
+	return len(s.members)
 }
 
-func (s *surrealSet) insert(num surrealNumber) {
-    if !s.isMember(num) {
-        s.members = append(s.members, num)
-    }
+func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) {
+	if !s.isMember(num, u) {
+		s.members = append(s.members, num)
+	}
 }
 
-func (s *surrealSet) remove(num surrealNumber) {
-    for i := 0; i < len(s.members); i++ {
-        if num.number == s.members[i].number {
-            s.members[i] = s.members[len(s.members)-1]
-            s.members = s.members[:len(s.members)-1]
-        }
-    }
+func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) {
+	for i := 0; i < len(s.members); i++ {
+		if u.equal(num, s.members[i]) {
+			s.members[i] = s.members[len(s.members)-1]
+			s.members = s.members[:len(s.members)-1]
+		}
+	}
 }
 
 // =============================================================================
 
 func main() {
-    // Obtain termination conditions from user.
-    remainingGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
-    flag.Parse()
-    if *remainingGenerations < 1 {
-        log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
-    }
-
-    // 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.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})
-
-    for generation := 1; generation <= *remainingGenerations; generation++ {
-        potentialNumbers := permuteExistingNumbers(generation, universe)
-        validNumbers := pruneInvalidNumbers(potentialNumbers, universe)
-        addNumbersToUniverse(validNumbers, &universe)
-    }
-
-    // TODO: These are just for checking progress. How do I want to render the
-    // final generation vs magnitude chart?
-    fmt.Println("Total Numbers:", len(universe.numbers))
-    fmt.Println(universe.numbers)
+	// 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.")
 }
 
 // =============================================================================
@@ -201,66 +296,108 @@ func main() {
 // 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 {
-    var numbers []surrealNumber
-
-    // 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])
-            rightSet.insert(universe.numbers[j])
-            newSurrealNumber := surrealNumber{surrealValue{&leftSet,&rightSet},surrealMetadata{0,generation}}
-            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])
-        newSurrealNumber := surrealNumber{surrealValue{&tempSet,nil},surrealMetadata{0,generation}}
-        numbers = append(numbers, newSurrealNumber)
-        newSurrealNumber = surrealNumber{surrealValue{nil,&tempSet},surrealMetadata{0,generation}}
-        numbers = append(numbers, newSurrealNumber)
-    }
-
-    return numbers
-}
-
-func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber {
-    var numbers []surrealNumber
-    for i := 0; i < len(candidates); i++ {
-        if isValidSurrealNumber(candidates[i], universe) {
-            numbers = append(numbers, candidates[i])
-        }
-    }
-    return numbers
+	// 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 per Definition 3?
-    if candidate.number.leftSet.cardinality() > 1 || candidate.number.rightSet.cardinality() > 1 {
-        return false
-    }
-
-    // Is the number valid per Axiom 1?
-    if candidate.number.leftSet != nil && candidate.number.rightSet != nil {
-        // TODO: This needs to be beefed up since <|> = <-1|1>.
-        if candidate.number.leftSet == candiate.number.rightSet {
-            return false
-        }
-        if !universe.lessThanOrEqual(candidate.number.leftSet[0], candidate.number.rightSet[0]) {
-            return false
-        }
-    }
-
-    return true
+	// 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])
-    }
+	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
+}