Editing Signed-digit representation

{{Short description|Positional system with signed digits; the representation may not be unique}}
{{Numeral systems}}
{{distinguish|Signed number representations}}

In [[mathematical notation]] for [[number]]s, a '''signed-digit representation''' is a [[positional numeral system]] with a set of [[sign (mathematics)|sign]]ed [[numerical digit|digit]]s used to [[Code|encode]] the [[integers]].

Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries.<ref>Dhananjay Phatak, I. Koren (1994) [https://cs.umbc.edu/~phatak/publications/hsdtrc.pdf Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains]</ref>  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 [[John Colson|Colson]] (1726) and [[Augustin-Louis Cauchy|Cauchy]] (1840).<ref>[[Augustin-Louis Cauchy]] (16 November 1840) "Sur les moyens d'eviter les erreurs dans les calculs numerique", [[Comptes rendus]] 11:789. Also found in ''Oevres completes'' Ser. 1, vol. 5, pp.&nbsp;434&ndash;42.</ref> In his book ''History of Mathematical Notations'', Cajori titled the section "Negative numerals".<ref>{{cite book |last= Cajori |first=Florian |author-link=Florian Cajori|title= A History of Mathematical Notations |page= [https://archive.org/details/historyofmathema00cajo_0/page/57 57] |publisher= [[Dover Publications]] |year= 1993 |orig-year= 1928-1929 |isbn= 978-0486677668 | url = https://archive.org/details/historyofmathema00cajo_0|url-access= registration }}</ref> For completeness, Colson<ref>{{Cite journal |last=Colson |first=John |date=1726 |title=A Short Account of Negativo-Affirmative Arithmetick, by Mr. John Colson, F. R. S. |url=https://www.jstor.org/stable/103469 |journal=Philosophical Transactions |volume=34 |pages=161–173 |jstor=103469 |bibcode=1726RSPT...34..161C |issn=0260-7085}}</ref> uses examples and describes [[addition]] (pp.&nbsp;163–4), [[multiplication]] (pp.&nbsp;165–6) and [[division (mathematics)|division]] (pp.&nbsp;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]]<ref>Eduard Selling (1887) ''Eine neue Rechenmachine'', pp.&nbsp;15&ndash;18, Berlin</ref> 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]].<ref>Rudolf Mehmke (1902) "Numerisches Rechen", §4 Beschränkung in den verwendeten Ziffern, [[Klein's encyclopedia]], I-2, p.&nbsp;944.</ref>

==Definition and properties==
===Digit set===
Let <math>\mathcal{D}</math> be a [[finite set]] of [[numerical digits]] with [[cardinality]] <math>b > 1</math> (If <math>b \leq 1</math>, then the positional number system is [[Triviality (mathematics)|trivial]] and only represents the [[trivial ring]]), with each digit denoted as <math>d_i</math> for <math>0 \leq i < b.</math> <math>b</math> is known as the <em>[[radix]]</em> or <em>[[number base]]</em>. <math>\mathcal{D}</math> can be used for a signed-digit representation if it's associated with a unique [[Function (mathematics)|function]] <math>f_\mathcal{D}:\mathcal{D}\rightarrow\mathbb{Z}</math> such that <math>f_\mathcal{D}(d_i) \equiv i \bmod b</math> for all <math>0 \leq i < b.</math> 
This function, <math>f_{\mathcal{D}},</math> is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in <math>\mathcal{D}.</math> 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. 

<math>\mathcal{D}</math> can be [[Partition of a set|partitioned]] into three distinct sets <math>\mathcal{D}_{+}</math>, <math>\mathcal{D}_{0}</math>, and <math>\mathcal{D}_{-}</math>, representing the positive, zero, and negative digits respectively, such that all digits <math>d_{+}\in\mathcal{D}_{+}</math> satisfy <math>f_\mathcal{D}(d_{+}) > 0</math>, all digits <math>d_{0}\in\mathcal{D}_{0}</math> satisfy <math>f_\mathcal{D}(d_{0}) = 0</math> and all digits <math>d_{-}\in\mathcal{D}_{-}</math> satisfy <math>f_\mathcal{D}(d_{-}) < 0</math>. The cardinality of <math>\mathcal{D}_{+}</math> is <math>b_{+}</math>, the cardinality of <math>\mathcal{D}_{0}</math> is <math>b_{0}</math>, and the cardinality of <math>\mathcal{D}_{-}</math> is <math>b_{-}</math>, giving the number of positive and negative digits respectively, such that <math>b = b_{+} + b_{0} + b_{-}</math>. 

====Balanced form representations====
{{See also|Balanced ternary}}
Balanced form representations are representations where for every positive digit <math>d_{+}</math>, there exist a corresponding negative digit <math>d_{-}</math> such that <math>f_\mathcal{D}(d_{+}) = -f_\mathcal{D}(d_{-})</math>. It follows that <math>b_{+} = b_{-}</math>. Only [[odd number|odd]] bases can have balanced form representations, as otherwise <math>d_{b/2}</math> has to be the opposite of itself and hence 0, but <math>0\ne \frac b2</math>. In balanced form, the negative digits <math>d_{-}\in\mathcal{D}_{-}</math> are usually denoted as positive digits with a bar over the digit, as <math>d_{-} = \bar{d}_{+}</math> for <math>d_{+}\in\mathcal{D}_{+}</math>. For example, the digit set of [[balanced ternary]] would be <math>\mathcal{D}_{3} = \lbrace\bar{1},0,1\rbrace</math> with <math>f_{\mathcal{D}_{3}}(\bar{1}) = -1</math>, <math>f_{\mathcal{D}_{3}}(0) = 0</math>, and <math>f_{\mathcal{D}_{3}}(1) = 1</math>. This convention is adopted in [[finite field]]s of odd [[Prime number|prime]] order <math>q</math>:<ref>{{Cite book|title=Projective Geometries Over Finite Fields|first1=J. W. P.|last1=Hirschfeld|author-link=J. W. P. Hirschfeld|publisher=[[Oxford University Press]]|year=1979|page=8|isbn=978-0-19-850295-1}}</ref>
:<math>\mathbb{F}_{q} = \lbrace0, 1, \bar{1} = -1,... d = \frac{q - 1}{2},\ \bar{d} = \frac{1-q}{2}\ |\ q = 0\rbrace.</math>

====Dual signed-digit representation====
Every digit set <math>\mathcal{D}</math> has a [[Duality (order theory)|dual]] digit set <math>\mathcal{D}^\operatorname{op}</math> given by the [[inverse order]] of the digits with an [[isomorphism]] <math>g:\mathcal{D}\rightarrow\mathcal{D}^\operatorname{op}</math> defined by <math>-f_\mathcal{D} = g\circ f_{\mathcal{D}^\operatorname{op}}</math>. As a result, for any signed-digit representations <math>\mathcal{N}</math> of a number system [[Ring (mathematics)|ring]] <math>N</math> constructed from <math>\mathcal{D}</math> with [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{N}\rightarrow N</math>, there exists a dual signed-digit representations of <math>N</math>, <math>\mathcal{N}^\operatorname{op}</math>, constructed from <math>\mathcal{D}^\operatorname{op}</math> with [[Valuation (algebra)|valuation]] <math>v_{\mathcal{D}^\operatorname{op}}:\mathcal{N}^\operatorname{op}\rightarrow N</math>, and an isomorphism <math>h:\mathcal{N}\rightarrow\mathcal{N}^\operatorname{op}</math> defined by <math>-v_\mathcal{D} = h\circ v_{\mathcal{D}^\operatorname{op}}</math>, where <math>-</math> is the additive inverse operator of <math>N</math>. The digit set for balanced form representations is [[self-dual]].

===For integers===
Given the digit set <math>\mathcal{D}</math> and function <math>f:\mathcal{D}\rightarrow\mathbb{Z}</math> as defined above, let us define an [[integer]] [[endofunction]] <math>T:\mathbb{Z}\rightarrow\mathbb{Z}</math> as the following:
:<math>T(n) = 
\begin{cases}
\frac{n - f(d_i)}{b} &\text{if } n \equiv i \bmod b, 0 \leq i < b
\end{cases}</math>
If the only [[periodic point]] of <math>T</math> is the [[fixed point (mathematics)|fixed point]] <math>0</math>, then the set of all signed-digit representations of the [[integers]] <math>\mathbb{Z}</math> using <math>\mathcal{D}</math> is given by the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>m \in \mathcal{D}^+</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^+\rightarrow\mathbb{Z}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=0}^{n}f_\mathcal{D}(d_{i})b^{i}</math>. 
Examples include [[balanced ternary]] with digits <math>\mathcal{D} = \lbrace \bar{1}, 0, 1\rbrace</math>.  

Otherwise, if there exist a non-zero [[periodic point]] of <math>T</math>, then there exist integers that are represented by an infinite number of non-zero digits in <math>\mathcal{D}</math>. Examples include the standard [[decimal numeral system]] with the digit set <math>\operatorname{dec} = \lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \rbrace</math>, which requires an [[Radix complement|infinite number of the digit]] <math>9</math> to represent the [[additive inverse]] <math>-1</math>, as <math>T_\operatorname{dec}(-1) = \frac{-1 - 9}{10} = -1</math>, and the positional numeral system with the digit set <math>\mathcal{D} = \lbrace \text{A}, 0, 1\rbrace</math> with <math>f(\text{A}) = -4</math>, which requires an infinite number of the digit <math>\text{A}</math> to represent the number <math>2</math>, as <math>T_\mathcal{D}(2) = \frac{2 - (-4)}{3} = 2</math>.

===For decimal fractions===
{{Main|Decimal representation}}
If the integers can be represented by the [[Kleene plus]] <math>\mathcal{D}^+</math>, then the set of all signed-digit representations of the [[decimal fraction]]s, or [[Dyadic rational|<math>b</math>-adic rationals]] <math>\mathbb{Z}[1\backslash b]</math>, is given by <math>\mathcal{Q} = \mathcal{D}^+\times\mathcal{P}\times\mathcal{D}^*</math>, the [[Cartesian product]] of the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, the [[Singleton (mathematics)|singleton]] <math>\mathcal{P}</math> consisting of the [[radix point]] (<math>.</math> or <math>,</math>), and the [[Kleene star]] <math>\mathcal{D}^*</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{-1} \ldots d_{-m}</math>, with <math>m,n\in\mathbb{N}</math>. Each signed-digit representation <math>q \in \mathcal{Q}</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{Q}\rightarrow\mathbb{Z}[1\backslash b]</math>
:<math>v_\mathcal{D}(q) = \sum_{i=-m}^{n}f_\mathcal{D}(d_{i})b^{i}</math>

===For real numbers===
{{Main|Construction of the reals#Construction from Cauchy sequences}}
If the integers can be represented by the [[Kleene plus]] <math>\mathcal{D}^+</math>, then the set of all signed-digit representations of the [[real numbers]] <math>\mathbb{R}</math> is given by <math>\mathcal{R} = \mathcal{D}^+ \times \mathcal{P} \times \mathcal{D}^\mathbb{N}</math>, the [[Cartesian product]] of the [[Kleene plus]] <math>\mathcal{D}^+</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_n \ldots d_0</math> with at least one digit, the [[Singleton (mathematics)|singleton]] <math>\mathcal{P}</math> consisting of the [[radix point]] (<math>.</math> or <math>,</math>), and the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all [[infinity|infinite]] [[concatenation|concatenated]] strings of digits <math>d_{-1} d_{-2} \ldots</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>r \in \mathcal{R}</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{R}\rightarrow\mathbb{R}</math>
:<math>v_\mathcal{D}(r) = \sum_{i=-\infty}^{n}f_\mathcal{D}(d_{i})b^{i}</math>. 
The [[infinite series]] always [[Convergent series|converges]] to a finite real number.

===For other number systems===
All base-<math>b</math> numerals can be represented as a subset of <math>\mathcal{D}^\mathbb{Z}</math>, the set of all [[doubly infinite sequence]]s of digits in <math>\mathcal{D}</math>, where <math>\mathbb{Z}</math> is the set of [[integers]], and the [[Ring (mathematics)|ring]] of base-<math>b</math> numerals is represented by the [[formal power series ring]] <math>\mathbb{Z}[[b,b^{-1}]]</math>, the doubly infinite series
:<math>\sum_{i = -\infty}^{\infty}a_i b^i</math>
where <math>a_i\in\mathbb{Z}</math> for <math>i\in\mathbb{Z}</math>. 

====Integers modulo powers of {{math|''b''}}====
The set of all signed-digit representations of the [[Integers modulo n|integers modulo <math>b^n</math>]], <math>\mathbb{Z}\backslash b^n\mathbb{Z}</math> is given by the set <math>\mathcal{D}^n</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{n - 1} \ldots d_0</math> of length <math>n</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^n\rightarrow\mathbb{Z}/b^n\mathbb{Z}</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=0}^{n - 1}f_\mathcal{D}(d_{i})b^{i} \bmod b^n</math>

====Prüfer groups====
A [[Prüfer group]] is the [[quotient group]] <math>\mathbb{Z}(b^\infty) = \mathbb{Z}[1\backslash b]/\mathbb{Z}</math> of the integers and the <math>b</math>-adic rationals. The set of all signed-digit representations of the [[Prüfer group]] is given by the [[Kleene star]] <math>\mathcal{D}^*</math>, the set of all finite [[concatenation|concatenated]] strings of digits <math>d_{1} \ldots d_{n}</math>, with <math>n\in\mathbb{N}</math>. Each signed-digit representation <math>p \in \mathcal{D}^*</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^*\rightarrow\mathbb{Z}(b^\infty)</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=1}^{n}f_\mathcal{D}(d_{i})b^{-i} \bmod 1</math>

====Circle group====
The [[circle group]] is the quotient group <math>\mathbb{T} = \mathbb{R}/\mathbb{Z}</math> of the integers and the real numbers. The set of all signed-digit representations of the [[circle group]] is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all right-infinite concatenated strings of digits <math>d_{1} d_{2} \ldots</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{N}\rightarrow\mathbb{T}</math>
:<math>v_\mathcal{D}(m) \equiv \sum_{i=1}^{\infty}f_\mathcal{D}(d_{i})b^{-i} \bmod 1</math>
The [[infinite series]] always [[Convergent series|converges]].

===={{math|''b''}}-adic integers====
The set of all signed-digit representations of the [[p-adic integers|<math>b</math>-adic integers]], <math>\mathbb{Z}_b</math> is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{N}</math>, the set of all left-infinite concatenated strings of digits <math>\ldots d_{1} d_{0}</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{N}\rightarrow\mathbb{Z}_{b}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=0}^{\infty}f_\mathcal{D}(d_{i})b^{i}</math>

===={{math|''b''}}-adic solenoids====
The set of all signed-digit representations of the [[Solenoid (mathematics)#p-adic solenoids|<math>b</math>-adic solenoids]], <math>\mathbb{T}_b</math> is given by the [[Cantor space]] <math>\mathcal{D}^\mathbb{Z}</math>, the set of all [[doubly infinite]] concatenated strings of digits <math>\ldots d_{1} d_{0} d_{-1} \ldots</math>. Each signed-digit representation <math>m \in \mathcal{D}^n</math> has a [[Valuation (algebra)|valuation]] <math>v_\mathcal{D}:\mathcal{D}^\mathbb{Z}\rightarrow\mathbb{T}_{b}</math>
:<math>v_\mathcal{D}(m) = \sum_{i=-\infty}^{\infty}f_\mathcal{D}(d_{i})b^{i}</math>

==In written and spoken language==
===Indo-Aryan languages===
The oral and written forms of numbers in the [[Indo-Aryan languages]] use a negative numeral (e.g., "un" in [[Hindi]] and [[Bengali language|Bengali]], "un" or "unna" in [[Punjabi_Language|Punjabi]], "ekon" in [[Marathi_Language|Marathi]]) for the numbers between 11 and 90 that end with a nine. The numbers followed by their names are shown for Punjabi below (the prefix "ik" means "one"):<ref>[http://quizlet.com/16314536/punjabi-numbers-1-100-flash-cards/ Punjabi numbers] from [[Quizlet]]</ref> 
* 19 unni, 20 vih, 21 ikki
* 29 unatti, 30 tih, 31 ikatti
* 39 untali, 40 chali, 41 iktali
* 49 unanja, 50 panjah, 51 ikvanja
* 59 unahat, 60 sath, 61 ikahat
* 69 unattar, 70 sattar, 71 ikhattar
* 79 unasi, 80 assi, 81 ikiasi
* 89 unanve, 90 nabbe, 91 ikinnaven.

Similarly, the [[Sesotho]] language utilizes negative numerals to form 8's and 9's.
* 8 robeli (/Ro-bay-dee/)  meaning "break two" i.e. two fingers down
* 9 robong (/Ro-bong/) meaning "break one" i.e. one finger down

===Classical Latin===
In [[Classical Latin]],<ref>J. Matthew Harrington (2016) [https://cpb-us-w2.wpmucdn.com/campuspress.yale.edu/dist/4/3253/files/2018/08/Harrington-Latin-Grammar-2016.pdf Synopsis of Ancient Latin Grammar]</ref> integers 18 and 19 did not even have a spoken, nor written form including corresponding parts for "eight" or "nine" in practice - despite them being in existence. Instead, in Classic Latin,

*18 = duodēvīgintī ("two taken from twenty"), (IIXX or XIIX),
*19 = ūndēvīgintī ("one taken from twenty"), (IXX or XIX)
*20 = vīgintī ("twenty"), (XX).

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:<ref>{{Citation |title=duodetriginta |date=2020-03-25 |work=Wiktionary, the free dictionary |url=https://en.wiktionary.org/w/index.php?title=duodetriginta&oldid=58999568 |access-date=2024-04-07 |language=en}}</ref>

*28 = duodētrīgintā ("two taken from thirty"), less frequently also yet vīgintī octō / octō et vīgintī ("twenty eight / eight and twenty"), (IIXXX or XXIIX versus XXVIII, latter having been fully outcompeted.)
*29 = ūndētrīgintā ("one taken from thirty") despite the less preferred form was also at their disposal.

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.

===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:<ref>{{Cite web |title=Kielitoimiston sanakirja |url=https://www.kielitoimistonsanakirja.fi/#/perusluku |access-date=2024-04-07 |website=www.kielitoimistonsanakirja.fi}}</ref>

*1 = "yksi" (Note: yhd- or yht- mostly when about to be declined; e.g. "yhdessä" = "together, as one [entity]")
*2 = "kaksi" (Also note: kahde-, kahte- when declined)
*3 = "kolme"
*4 = "neljä"
...
*7 = "seitsemän"
*8 = "kah(d)eksan" (two left [for it to reach it])
*9 = "yh(d)eksän" (one left [for it to reach it])
*10 = "kymmenen" (ten)

Above list is no special case, it consequently appears in larger cardinals as well, e.g.:
*399 = "kolmesataayhdeksänkymmentäyhdeksän"

Emphasizing of these attributes stay present even in the shortest colloquial forms of numerals:

*1 = "yy"
*2 = "kaa"
*3 = "koo"
...
*7 = "seiska"
*8 = "kasi"
*9 = "ysi"
*10 = "kymppi"

However, this phenomenon has no influence on written numerals, the Finnish use the standard Western-Arabic decimal notation.

===Time keeping===
In the [[English language]] it is common to refer to times as, for example, 'seven to three', 'to' performing the negation.

==Other systems==
There exist other signed-digit bases such that the base <math>b \neq b_{+} + b_{-} + 1</math>. A notable examples of this is [[Booth encoding]], which has a digit set <math>\mathcal{D} = \lbrace\bar{1},0,1\rbrace</math> with <math>b_{+} = 1</math> and <math>b_{-} = 1</math>, but which uses a base <math>b = 2 < 3 = b_{+} + b_{-}  + 1</math>. The standard [[binary numeral system]] would only use digits of value <math>\lbrace0,1\rbrace</math>.

Note that non-standard signed-digit representations are not unique.  For instance:

: <math>0111_{\mathcal{D}} = 4 + 2 + 1 = 7</math>
: <math>10\bar{1}1_{\mathcal{D}} = 8 - 2 + 1 = 7</math>
: <math>1\bar{1}11_{\mathcal{D}} = 8 - 4 + 2 + 1 = 7</math>
: <math>100\bar{1}_{\mathcal{D}} = 8 - 1 = 7</math>

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 decimal#Extension to other bases|repeating binary]] numbers in NAF,
: <math>\frac{2}{3} = 0.\overline{10}_{\mathcal{D}} = 1.\overline{0\bar{1}}_{\mathcal{D}}</math>

==See also==
* [[Balanced ternary]]
* [[Negative base]]
* [[Redundant binary representation]]

==Notes and references==
{{reflist}}

* J. P. Balantine (1925) "A Digit for Negative One", [[American Mathematical Monthly]] 32:302.
* Lui Han, Dongdong Chen, Seok-Bum Ko, Khan A. Wahid [http://homepage.usask.ca/~doc220/index_files/doc/C12.pdf "Non-speculative Decimal Signed Digit Adder"] from Department of Electrical and Computer Engineering, [[University of Saskatchewan]].

{{Authority control}}
{{Use dmy dates|date=December 2020}}

{{DEFAULTSORT:Signed-Digit Representation}}
[[Category:Non-standard positional numeral systems]]
[[Category:Number theory]]
[[Category:Ring theory]]
[[Category:Arithmetic dynamics]]
[[Category:Coding theory]]
[[Category:Formal languages]]
[[Category:Sign (mathematics)]]