Signed-digit representation

In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.
Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries. In the binary numeral system, a special case signed-digit representation is the "non-adjacent form", which can offer speed benefits with minimal space overhead.
History.
Challenges in calculation stimulated early authors Colson (1726) and Cauchy (1840) to use signed-digit representation. The further step of replacing negated digits with new ones was suggested by Selling (1887) and Cajori (1928).
In 1928, Florian Cajori noted the recurring theme of signed digits, starting with Colson (1726) and Cauchy (1840). In his book "History of Mathematical Notations", Cajori titled the section "Negative numerals". For completeness, Colson uses examples and describes addition (pp. 163–4), multiplication (pp. 165–6) and division (pp. 170–1) using a table of multiples of the divisor. He explains the convenience of approximation by truncation in multiplication. Colson also devised an instrument (Counting Table) that calculated using signed digits.
Eduard Selling advocated inverting the digits 1, 2, 3, 4, and 5 to indicate the negative sign. He also suggested "snie", "jes", "jerd", "reff", and "niff" as names to use vocally. Most of the other early sources used a bar over a digit to indicate a negative sign for a it. Another German usage of signed-digits was described in 1902 in Klein's encyclopedia.
Definition and properties.
Digit set.
Let formula_1 be a finite set of numerical digits with cardinality formula_2 (If formula_3, then the positional number system is trivial and only represents the trivial ring), with each digit denoted as formula_4 for formula_5 formula_6 is known as the radix or number base. formula_1 can be used for a signed-digit representation if it's associated with a unique function formula_8 such that formula_9 for all formula_5 
This function, formula_11 is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in formula_12 One benefit of this formalism is that the definition of "the integers" (however they may be defined) is not conflated with any particular system for writing/representing them; in this way, these two distinct (albeit closely related) concepts are kept separate. 
formula_1 can be partitioned into three distinct sets formula_14, formula_15, and formula_16, representing the positive, zero, and negative digits respectively, such that all digits formula_17 satisfy formula_18, all digits formula_19 satisfy formula_20 and all digits formula_21 satisfy formula_22. The cardinality of formula_14 is formula_24, the cardinality of formula_15 is formula_26, and the cardinality of formula_16 is formula_28, giving the number of positive and negative digits respectively, such that formula_29. 
Balanced form representations.
Balanced form representations are representations where for every positive digit formula_30, there exist a corresponding negative digit formula_31 such that formula_32. It follows that formula_33. Only odd bases can have balanced form representations, as when formula_33 then formula_35 will be an odd number. In balanced form, the negative digits formula_21 are usually denoted as positive digits with a bar over the digit, as formula_37 for formula_17. For example, the digit set of balanced ternary would be formula_39 with formula_40, formula_41, and formula_42. This convention is adopted in finite fields of odd prime order formula_43:
Dual signed-digit representation.
Every digit set formula_1 has a dual digit set formula_46 given by the inverse order of the digits with an isomorphism formula_47 defined by formula_48. As a result, for any signed-digit representations formula_49 of a number system ring formula_50 constructed from formula_1 with valuation formula_52, there exists a dual signed-digit representations of formula_50, formula_54, constructed from formula_46 with valuation formula_56, and an isomorphism formula_57 defined by formula_58, where formula_59 is the additive inverse operator of formula_50. The digit set for balanced form representations is self-dual.
For integers.
Given the digit set formula_1 and function formula_62 as defined above, let us define an integer endofunction formula_63 as the following:
If the only periodic point of formula_65 is the fixed point formula_66, then the set of all signed-digit representations of the integers formula_67 using formula_1 is given by the Kleene plus formula_69, the set of all finite concatenated strings of digits formula_70 with at least one digit, with formula_71. Each signed-digit representation formula_72 has a valuation formula_73
Examples include balanced ternary with digits formula_75. 
Otherwise, if there exist a non-zero periodic point of formula_65, then there exist integers that are represented by an infinite number of non-zero digits in formula_1. Examples include the standard decimal numeral system with the digit set formula_78, which requires an infinite number of the digit formula_79 to represent the additive inverse formula_80, as formula_81, and the positional numeral system with the digit set formula_82 with formula_83, which requires an infinite number of the digit formula_84 to represent the number formula_85, as formula_86.
For decimal fractions.
If the integers can be represented by the Kleene plus formula_69, then the set of all signed-digit representations of the decimal fractions, or formula_6-adic rationals formula_89, is given by formula_90, the Cartesian product of the Kleene plus formula_69, the set of all finite concatenated strings of digits formula_70 with at least one digit, the singleton formula_93 consisting of the radix point (formula_94 or formula_95), and the Kleene star formula_96, the set of all finite concatenated strings of digits formula_97, with formula_98. Each signed-digit representation formula_99 has a valuation formula_100
For real numbers.
If the integers can be represented by the Kleene plus formula_69, then the set of all signed-digit representations of the real numbers formula_103 is given by formula_104, the Cartesian product of the Kleene plus formula_69, the set of all finite concatenated strings of digits formula_70 with at least one digit, the singleton formula_93 consisting of the radix point (formula_94 or formula_95), and the Cantor space formula_110, the set of all infinite concatenated strings of digits formula_111, with formula_71. Each signed-digit representation formula_113 has a valuation formula_114
The infinite series always converges to a finite real number.
For other number systems.
All base-formula_6 numerals can be represented as a subset of formula_117, the set of all doubly infinite sequences of digits in formula_1, where formula_67 is the set of integers, and the ring of base-formula_6 numerals is represented by the formal power series ring formula_121, the doubly infinite series
where formula_123 for formula_124. 
Integers modulo formula_125.
The set of all signed-digit representations of the integers modulo formula_125, formula_127 is given by the set formula_128, the set of all finite concatenated strings of digits formula_129 of length formula_130, with formula_71. Each signed-digit representation formula_132 has a valuation formula_133
Prüfer groups.
A Prüfer group is the quotient group formula_135 of the integers and the formula_6-adic rationals. The set of all signed-digit representations of the Prüfer group is given by the Kleene star formula_96, the set of all finite concatenated strings of digits formula_138, with formula_71. Each signed-digit representation formula_140 has a valuation formula_141
Circle group.
The circle group is the quotient group formula_143 of the integers and the real numbers. The set of all signed-digit representations of the circle group is given by the Cantor space formula_110, the set of all right-infinite concatenated strings of digits formula_145. Each signed-digit representation formula_132 has a valuation formula_147
The infinite series always converges.
formula_6-adic integers.
The set of all signed-digit representations of the formula_6-adic integers, formula_151 is given by the Cantor space formula_110, the set of all left-infinite concatenated strings of digits formula_153. Each signed-digit representation formula_132 has a valuation formula_155
formula_6-adic solenoids.
The set of all signed-digit representations of the formula_6-adic solenoids, formula_159 is given by the Cantor space formula_117, the set of all doubly infinite concatenated strings of digits formula_161. Each signed-digit representation formula_132 has a valuation formula_163
In written and spoken language.
The oral and written forms of numbers in the Punjabi language use a form of a negative numeral one written as "una" or "un". This negative one is used to form 19, 29, …, 89 from the root for 20, 30, …, 90. Explicitly, here are the numbers:
Similarly, the Sesotho language utilizes negative numerals to form 8's and 9's.
Classic Latin - Ancient Rome
In Classic Latin, integers 18 and 19 even didn't have a spoken, nor written form including corresponding parts for "eight" or "nine" in practice - despite them being in existence. Instead, in Classic Latin,
For upcoming integer numerals [28, 29, 38, 39, ..., 88, 89] the additive form in the language had been much more common, however, for the listed numbers, the above form was still preferred. Hence, approaching thirty, numerals were expressed as:
This is one of the main foundations of contemporary historians' reasoning, explaining why the subtractive I- and II- was so common in this range of cardinals compared to other ranges. Numerals 98 and 99 could also be expressed in both forms, yet "two to hundred" might have sounded a bit odd - clear evidence is the scarce occurrence of these numbers written down in a subtractive fashion in authentic sources.
In the Finnish Language
There is yet another language having this feature (by now, only in traces), however, still in active use today. This is the Finnish Language, where the (spelled out) numerals are used this way should a digit of 8 or 9 occur. The scheme is like this:
Above list is no special case, it consequently appears in larger cardinals as well, e.g.:
Emphasizing of these attributes stay present even in the shortest colloquial forms of numerals:
However, this phenomenon has no influence on written numerals, the Finnish use the standard Western-Arabic decimal notation.
In the English language it is common to refer to times as, for example, 'seven til three', 'til' performing the negation.
Other systems.
There exist other signed-digit bases such that the base formula_165. A notable examples of this is Booth encoding, which has a digit set formula_166 with formula_167 and formula_168, but which uses a base formula_169. The standard binary numeral system would only use digits of value formula_170.
Note that non-standard signed-digit representations are not unique. For instance:
The non-adjacent form (NAF) of Booth encoding does guarantee a unique representation for every integer value. However, this only applies for integer values. For example, consider the following repeating binary numbers in NAF,