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 A 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 it. Another German usage of signed-digits was described in 1902 in Klein's encyclopedia.
Definition and properties
Digit set Let D {\displaystyle {\mathcal {D}}} be a finite set of numerical digits with cardinality b > 1 {\displaystyle b>1} (If b ≤ 1 {\displaystyle b\leq 1} , then the positional number system is trivial and only represents the trivial ring), with each digit denoted as d i {\displaystyle d_{i}} for 0 ≤ i < b . {\displaystyle 0\leq i<b.} b {\displaystyle b} is known as the radix or number base. D {\displaystyle {\mathcal {D}}} can be used for a signed-digit representation if it's associated with a unique function f D : D → Z {\displaystyle f_{\mathcal {D}}:{\mathcal {D}}\rightarrow \mathbb {Z} } such that f D ( d i ) ≡ i mod b {\displaystyle f_{\mathcal {D}}(d_{i})\equiv i{\bmod {b}}} for all 0 ≤ i < b . {\displaystyle 0\leq i<b.} This function, f D , {\displaystyle f_{\mathcal {D}},} is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in D . {\displaystyle {\mathcal {D}}.} 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.
… excerpt ends here. Continue reading the full article.
