Bijective Base Representation

I wanted to convert a large number of string representations of common Base 10 number to Bijective Base 10. I found a textual method of creating the Bijective Base 10 string representations from Base 10 string representations.

Bijective Base 10 does not use the 0 (zero) digit anywhere. It has an extra digit, represented with A, that has a value of ten.

Base 10	Bijective Base 10
1	1
2	2
3	3
8	8
9	9
10	A
11	11
12	12
19	19
20	1A
21	21
22	22
99	99
100	9A
200	19A
1000	99A
1110	AAA

See that 1000₁₀ and 1110₁₀ have Bijective Base 10 representations that are only 3 digits.

I used the Go programming language which has a string type and a rune numeric type. A string is quickly and easily convertible to a slice of rune, and slices of rune can be converted to string.

The algorithm goes like this:

1. Convert string representation of an integer to []rune. The values of the slice of rune are place values, each plus a constant.
2. Make the values at each slice index into the place value: runes[i] -= '0'. This conversion causes a '0' character at some index to have a 0 value, a '9' character at another index will have a value of 9.
3. Check each index from left to right, starting at index 1, for a 0 value. If you find a 0 value at some index, subtract 1 from the value at the index to the left (next higher place). Set the 0-valued index to have a value of 10. Note that you found a zero.
4. Once you get to the rightmost index (least significant place), recall if you found one or more zero valued indexes. If you did, do step (3) again.
5. If you didn’t find any zeros, quit looping over the slice of rune.
6. If the most significant index has a zero value, re-index the slice of rune one to the left.
7. Add '0' to every index of the slice of rune, except those that have a value of 10. Make that index into 'A'.
8. Convert slice of rune back to a string.

    places := []rune(stringRepresention) // step 1
	for i := range places {
		places[i] -= '0'  // step 2, convert each place character to its value
	}
	foundZero := true
	for foundZero { // step 4 and step 5
		foundZero = false
		for i := 1; i < len(places); i++ {  // step 3
			if places[i] == 0 {
				places[i-1]--
				places[i] += 10
				foundZero = true  // note that we found a zero
			}
		}
	}
	if places[0] == 0 {
		places = places[1:] // step 6
	}
	for i := range places {  // step 7, convert place value to its character
		if i > 0 && places[i] == 10 {
			places[i] = 'A'
		} else {
			places[i] += '0'
		}
	}
    bijectiveRep := string(places)  // step 8

I think this is O(n²) in the worst case, n being the number of digits in the base 10 string representation. I think it’s O(n) in strings with no more than one ‘0’ character.

Best case inputs don’t have a '0' digit in their string representations. A single pass with no substitutions suffices.

The worst case inputs are numbers with string representations that are alternating '1' and '0' characters (101010₁₀), and numbers that have prefixes of '1' digits, and a final, least significant '0' digit (11110₁₀). Each '0' becomes an 'A', and the '1' to its left becomes a '0', necessitating another pass over the string.

No “place” gets decremented more than once. That means that a zero-valued place only gets created where a 1-valued place is immediately to the left of a zero-valued place.

The most significant digit is the only place that can have a zero-value at the end of the algorithm. There’s no place to its left to borrow a 10 from.

The above algorithm doesn’t make a number out of a Base 10 string representation. It works with individual place values, not with entire numbers. There’s no opportunity to overflow a register.

As far as the code goes, this seems like one of the rare cases where a do-while loop would be clearer.

---

Converting a Bijective Base 10 string representation into a numerical value is almost as simple as converting a Base 10 string into a number.

func convertBijective(runes []rune) int {
    number := 0
    for _, r := range runes {
        number = number * 10
        if r == 'A' {
            number += 10
        } else {
            number += int(r - '0')
        }
    }
    return number
}