// =============================================================================
-// 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?
+ // The elements in this slice are stored in order according to Axiom 3.
+ // Thus, numbers[0] < numbers[1] < ... < numbers[n].
numbers []surrealNumber
- nextUniqueID int
+ 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.
+func (u *surrealUniverse) getIndex(num surrealNumber) int {
for i := 0; i < len(u.numbers); i++ {
- if num.number == u.numbers[i].number {
- return true, i
+ if num.identifier == u.numbers[i].identifier {
+ return i
}
}
- return false, 0
+ return -1 // This should be unreachable.
}
func (u *surrealUniverse) cardinality() int {
}
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.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])
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ if index+1 == u.cardinality() {
+ u.numbers = append(u.numbers, num)
+ }
+ } else {
+ index := u.getIndex(num.rightSet.members[0])
+ num.identifier = u.nextUniqueID
+ u.nextUniqueID++
+ if index == 0 {
+ 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.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 {
+func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool {
+ if u.isRelated(numA, numB) && u.isRelated(numB, numA) {
return true
- } else {
- return false
}
+ 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)
}
-// 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) lessThan(left, right surrealNumber) bool {
+ return u.lessThanOrEqual(left, right) && !u.equal(left, right)
}
-type surrealMetadata struct {
- identifier int
- generation int
+func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool {
+ return !u.lessThan(left, right)
+}
+
+func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
+ return !u.isRelated(left, right)
}
// =============================================================================
+type surrealNumber struct {
+ leftSet surrealSet
+ rightSet surrealSet
+ identifier uint
+ generation int
+}
+
type surrealSet struct {
members []surrealNumber
}
-func (s *surrealSet) isMember(num surrealNumber) bool {
+func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool {
for i := 0; i < len(s.members); i++ {
- if num.number == s.members[i].number {
+ if u.equal(num, s.members[i]) {
return true
}
}
return len(s.members)
}
-func (s *surrealSet) insert(num surrealNumber) {
- if !s.isMember(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) {
+func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) {
for i := 0; i < len(s.members); i++ {
- if num.number == s.members[i].number {
+ 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.")
+ totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
flag.Parse()
- if *remainingGenerations < 1 {
+ if *totalGenerations < 1 {
log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
}
+ remainingGenerations := *totalGenerations - 1
// 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}})
+ universe.nextUniqueID = 0
+ universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0, 0})
- for generation := 1; generation <= *remainingGenerations; generation++ {
+ // Breed however many generations of numbers were requested by the user and
+ // add them all to the universe.
+ for generation := 1; generation <= remainingGenerations; generation++ {
+ // First generate all possible reduced form symbols per Axiom 1.
potentialNumbers := permuteExistingNumbers(generation, universe)
+ // Now prune out any symbols which are NOT valid numbers per Axiom 2.
validNumbers := pruneInvalidNumbers(potentialNumbers, universe)
+ // Attempt to add the new numbers to the universe. Any duplicates will
+ // be weeded out in the attempt.
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)
+ // Print the number line with generation on the horizontal axis and
+ // magnitude on the vertical axis.
+ 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.")
}
// =============================================================================
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}}
+ leftSet.insert(universe.numbers[i], universe)
+ rightSet.insert(universe.numbers[j], universe)
+ newSurrealNumber := surrealNumber{leftSet,rightSet,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}}
+ tempSet.insert(universe.numbers[i], universe)
+ newSurrealNumber := surrealNumber{tempSet,surrealSet{},0,generation}
numbers = append(numbers, newSurrealNumber)
- newSurrealNumber = surrealNumber{surrealValue{nil,&tempSet},surrealMetadata{0,generation}}
+ newSurrealNumber = surrealNumber{surrealSet{},tempSet,0,generation}
numbers = append(numbers, newSurrealNumber)
}
// 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 {
+ // Is the number in reduced form?
+ if candidate.leftSet.cardinality() > 1 || candidate.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
+ // 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
+ }
+ }
}
}
}
}
+// 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
+}