From 90f47767d2ca1ebed53e28ea2405864da8f4a640 Mon Sep 17 00:00:00 2001 From: Aaron Taylor Date: Sun, 9 May 2021 04:16:05 -0700 Subject: [PATCH] Final commit of 'initial version' of program for breeding surreal numbers. Program compiles and runs. Data output starts to become significant around generation 12-ish. --- chapter-1-experiments/ch1-breeding-numbers.go | 331 +++++++++++------- 1 file changed, 213 insertions(+), 118 deletions(-) diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go index b990361..9e9e637 100644 --- a/chapter-1-experiments/ch1-breeding-numbers.go +++ b/chapter-1-experiments/ch1-breeding-numbers.go @@ -11,28 +11,36 @@ import ( // ============================================================================= -// 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 { @@ -40,109 +48,139 @@ 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 } } @@ -153,15 +191,15 @@ func (s *surrealSet) cardinality() int { 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] } @@ -172,27 +210,38 @@ func (s *surrealSet) remove(num surrealNumber) { 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.") } // ============================================================================= @@ -207,19 +256,19 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN 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) } @@ -239,19 +288,20 @@ func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) [ // 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 + } + } } } @@ -264,3 +314,48 @@ func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) { } } +// 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 +} -- 2.20.1