A is a symbol or group of symbols that represents a number. The symbols “11(decimal)”, “1011(binary)” and “B(hexadecimal)” are numerals, all representing the number. The number is the idea, the numeral is anything that represents that idea. numeral Numerals are not the same as numbers just as words are not the same with the things they refer to. different same A positional numeral system denotes usually the extension to any of the (or ). In a more general sense, a positional system is a numeral system in which the to the value of a number is the . base Hindu–Arabic numeral system decimal system contribution of a digit value of the digit multiplied by a factor determined by the position of the digit In modern positional systems, such as the , the of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five , five , and five , respectively, due to their different in the digit string. decimal system position hundreds tens units positions According to its of occurrence in the number, each digit is . Towards the left, the weights increase by a constant factor equivalent to the or . With the help of the radix point (‘.’), the positions corresponding to integral weights (1) are differentiated from the positions corresponding to fractional weights (<1). position weighted base radix Any integer value that is greater than or equal to two can be used as the base or . radix The digit position ’ ’ has weight . . n r ^n The largest value of digit position is always 1 less than the base value The value of a number is a weighted sum of its digits. For example: Decimal (0–9 digits with radix 10) 2056 value breakdown Hexadecimal(0–9 & A-F digits with radix 16) 171B value breakdown The general form of value breakdown, where b is the base or radix of the numeral system The Idea to package Quick Link I wanted to be able to and play around with without having to worry about the semantics of each system. At the end of the day, as we mentioned before can represent the . So even operations between numerals from different systems shouldn’t be an issue when they can be translated to represent the same numbers. implement any numeral system the representation of numbers multiple different numerals same number For some reason, an image from the movie flashed in my head. The where machine, the , came to life and the mechanical rotors started spinning. Imitation Game beloved moment in human history Alan Turing’s bombe A digit in any positional numeral system can be by the it can take. Each state has a and a . The of the is the while producing a . represented possible states next state previous state next state last state first state carry-over A data structure like a can effectively represent what we mentioned in the above paragraph. circular list , . In a doubly-linked circular list the next pointer of the last node points to the first node, and the previous pointer of the first node points to the last node making the circular in both directions Here comes Go’s . With the ring, we can easily represent of by filling it with the possible ordered states and an initial value. ring any single digit any positional numeral system { r := ring.New( (values)) _, e := values { r.Value = e r = r.Next() } indexOf(state, values) == { , fmt.Errorf( , state, values) } values { r.Value == state { } r = r.Next() } r, } // newDigit creates and initializes a new digit (ring). func newDigit (values [] , state ) rune rune (*ring.Ring, error) // initialize a new empty ring len // fill the ring with values for range if -1 return nil "invalid digit. value: %v does not exist in possible values: %v" // roll the ring in desired "state" position. for range if break return nil What happens when a numeral contains more than one digit? That can easily be solved by having a whose elements would be consisted of doubly-linked list doubly-linked circular list s. This way we can easily create positional representation of any number. any { number := Numeral{ digits: list.New(), digitValues: values, } i := ; i < (initial); i++ { digit, err := newDigit(values, (initial[i])) err != { , err } number.digits.PushBack(digit) } &number, } // NewNumeral initializes a numeral by providing the initial number in strings // along with the possible values that each digit can have. func NewNumeral (values [] , initial ) rune string (*Numeral, error) // initialise a new number. // add digits to the number along with their state. for 0 len rune if nil return nil return nil Every time a resets back to the “first” state it would trigger a to the next most valuable digit. Pretty simple right? digit Next() In the case that our digits are all full and we want to increment, we can just create a new ring, initialize it and link it to the left side of our list. Think of an example, a hypothetical numeral system with which has a , and also imagine that we want to have a 4 “digit numeral” like “2z3r”. symbols [0–9,a-z] radix of 36 Numeral { digits *list.List digitValues [] } // Numeral represents a numeral that is consisted by its digits // and digit values. type struct rune By defining a number like this all you need to have is a you want to your number . slice of the symbols represent in the order they will have to exist values= [] { , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , } var rune '0' '1' '2' '3' '4' '5' '6' '7' '8' '9' 'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 'j' 'k' 'l' 'm' 'n' 'o' 'p' 'q' 'r' 's' 't' 'u' 'v' 'w' 'x' 'y' 'z' Then you need a “constructor” to generate numerals at will. { number := Numeral{ digits: list.New(), digitValues: values, } i := ; i < (initial); i++ { digit, err := newDigit(values, (initial[i])) err != { , err } number.digits.PushBack(digit) } &number, } // NewNumeral initializes a numeral by providing the initial number in strings // along with the possible values that each digit can have. func NewNumeral (values [] , initial ) rune string (*Numeral, error) // initialise a new number. // add digits to the number along with their state. for 0 len rune if nil return nil return nil Initializing a numeral after we have reached this point is pretty straightforward. number, _ := numeral.NewNumeral(values, ) "2z3r" Performing Simple Operations This approach makes +1 and -1 operations since always know their next and previous node. very fast lists (either circular or not) For example: Incrementing a numeral by needs to execute The result is “12d5”. Hexadecimal “12d4” one 1 next() to the rightmost ring, that's all. Incrementing a numeral “ ” by needs to execute . The result is “e000”. Hexadecimal dfff one 4 next() calls on the 3 rightmost rings and one last on the 4th most significant ring Decrementing1will operate in a similar way. { e := n.digits.Back(); e != ; e = e.Prev() { r := e.Value.(*ring.Ring) r = r.Next() e.Value = r r.Value != n.digitValues[ ] { } e.Prev() == { d, _ := newDigit(n.digitValues, n.digitValues[ ]) n.digits.PushFront(d) } } } // Increment performs a +1 to the Numeral. func (n *Numeral) Increment () error // take the first digit from the right and keep going if there are any arithmetic holdings. for nil // get current ring. // rotate and update. // if the digit is not being reset (no arithmetic holdings) then there is no need to // proceed in adding on the others. if 0 break // If needed add an extra new digit on the left side. if nil 0 return nil Adding and Subtracting can also happen efficiently even between numerals that are based on different systems by using the most known numbers of the decimal system that our computers easily understand. will just require both of those to , add them and generate a new numeral from the . The result numeral can even be on a different numeral system easily by generating it from an integer. Adding 2 numerals converting decimal integers result Converting any numeral to integer is easy by performing a value breakdown { dec := di := d := n.digits.Back(); d != ; d = d.Prev() { r := d.Value.(*ring.Ring) i := indexOf(r.Value.( ), n.digitValues) dec = dec + i*powInt( (n.digitValues), di) di++ } dec } // Decimal converts a numeral to a decimal integer. func (n *Numeral) Decimal () int 0 0 for nil // get current ring. // get the index of the ring. rune // Add digit's decimal counterpart to the decimal sum. len return Let’s Talk Numbers Running some on the method for for different initial values (small and big) results in some very nice results. The average execution time of the Increment function for binary numerals after 1 billion increments is around 7.6ns / op. benchmarks Increment() 3 different numeral systems As one may expect, therefore the transitions that need to happen are (increments/decrements)which results in better performance. selecting a numeral system with a higher numeral range results in carryovers appearing less frequently, fewer goos: linux goarch: amd64 pkg: github.com/slysterous/numeral cpu: Intel(R) Core(TM) i7– CPU @ GHz BenchmarkNumeralIncrementDecimalSmall ns/op BenchmarkNumeralIncrementDecimalLarge ns/op BenchmarkNumeralIncrementBinarySmall ns/op BenchmarkNumeralIncrementBinaryLarge ns/op BenchmarkNumeralIncrementHexSmall ns/op BenchmarkNumeralIncrementHexLarge ns/op 7700 3.60 -8 1000000000 4.604 -8 1000000000 4.574 -8 1000000000 7.644 -8 1000000000 7.655 -8 1000000000 4.427 -8 1000000000 4.652 How about converting numerals into decimal integers? From the benchmarks that I performed on Hex and Binary numerals, the process takes . The opposite process, converting from decimal ints to any numeral is similar. less than 1 μsecond Since converting to decimals , it’s easy to reach the conclusion that , . This can also be reflected in the below benchmark. requires traversing through every digit to sum its weight the more digits there are the slower the process will be go test -bench=NumeralDecimal -benchtime= s goos: linux goarch: amd64 pkg: github.com/slysterous/numeral cpu: Intel(R) Core(TM) i7– CPU @ GHz BenchmarkNumeralDecimalFromHex0– ns/op BenchmarkNumeralDecimalFromHexfffff ns/op BenchmarkNumeralDecimalFromHexffffffffff ns/op BenchmarkNumeralDecimalFromHexffffffffffffffffffff ns/op BenchmarkNumeralDecimalFromBinary0– ns/op BenchmarkNumeralDecimalFromBinary10000– ns/op BenchmarkNumeralDecimalFromBinary1000000000– ns/op BenchmarkNumeralDecimalFromBinary1000000000000000000– ns/op 60 7700 3.60 8 1000000000 8.182 -8 252367634 284.8 -8 250184980 286.0 -8 100000000 616.6 8 1000000000 7.818 8 837013039 84.98 8 337445121 214.8 8 158028769 455.9 Alright, one last check. How does adding numerals of different systems perform? Remember, I’m using decimal integers as the intermediate common base to perform operations. Turns out adding is also relatively fast since it to perform an average addition takes roughly around 8 μseconds Additions are a bit trickier in terms of performance. At least 2 conventions have to happen, both numbers are translated to decimal and in the end, the result is converted back to the final desired numeral system. This on the . relies heavily performance of the conversion of a numeral to decimal int go test -bench=NumeralAdd -benchtime= s goos: linux goarch: amd64 pkg: github.com/slysterous/numeral cpu: Intel(R) Core(TM) i7– CPU @ GHz BenchmarkNumeralAddBinaryOnHex ns/op BenchmarkNumeralAddHexOnHex ns/op BenchmarkNumeralAddDecOnDec ns/op BenchmarkNumeralAddSumBinaryOnHex ns/op BenchmarkNumeralAddSumHexOnHex ns/op BenchmarkNumeralAddSumDecOnDec ns/op 60 7700 3.60 -8 9691966 8651 -8 9144648 8290 -8 11384712 7014 -8 11281405 6237 -8 12745245 5873 -8 12672326 5849 In conclusion, is now a Go package. It gives you the ability to create custom (positional) numeral systems and perform operations on them. Feel free to contribute and don’t hesitate to reach out for any questions. numeral Also published on Medium's slysterous
