Updated getIndex() for 650% speed improvement in number breeding program.

[surreal-numbers] / chapter-1-experiments / ch1-breeding-numbers.go

// (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com>
// See LICENSE.txt file for copyright and license details.

package main

import (
    "flag"
    "fmt"
    "log"
    "os"
    "runtime/pprof"
    "sort"
    "strconv"
)

// =============================================================================

// 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 {
    // 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) 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)
}

func (u *surrealUniverse) insert(num surrealNumber) {
    // 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
            }
    }
}

// =============================================================================

// 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
}

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)
}

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)
}

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
    value float64
    identifier uint
    generation int
}

type surrealSet struct {
    members []surrealNumber
}

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)
}

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, 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() {
    // Flags to enable various performance profiling options.
    cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.")
    memProfilePrefix := flag.String("memprofileprefix", "", "Filename PREFIX 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 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)

        // Setup any memory profiling requested by the user. This will snapshot
        // the heap at the end of every generation.
        if *memProfilePrefix != "" {
            memProFile, err := os.Create(*memProfilePrefix + "-gen" + strconv.Itoa(generation) + ".mprof")
            if err != nil {
                log.Fatal("ERROR: Unable to write heap profile to disk:", err)
            }
            pprof.WriteHeapProfile(memProFile)
            memProFile.Close()
        }
    }
    fmt.Printf(".\n")


    // 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 {
    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], universe)
            rightSet.insert(universe.numbers[j], universe)
            newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,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], 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
}

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
}

// 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
}