Signed-digit representation

Definition and properties

Digit set

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

${\displaystyle \mathcal{D}}$ can be partitioned into three distinct sets ${\displaystyle {\mathcal{D}}_{+}}$, ${\displaystyle {\mathcal{D}}_0}$, and ${\displaystyle {\mathcal{D}}_{-}}$, representing the positive, zero, and negative digits respectively, such that all digits ${\displaystyle d_{+}\in {\mathcal{D}}_{+}}$ satisfy ${\displaystyle f_{\mathcal{D}}(d_{+})>0}$, all digits ${\displaystyle d_0\in {\mathcal{D}}_0}$ satisfy ${\displaystyle f_{\mathcal{D}}(d_0)=0}$ and all digits ${\displaystyle d_{-}\in {\mathcal{D}}_{-}}$ satisfy ${\displaystyle f_{\mathcal{D}}(d_{-})<0}$. The cardinality of ${\displaystyle {\mathcal{D}}_{+}}$ is ${\displaystyle b_{+}}$, the cardinality of ${\displaystyle {\mathcal{D}}_0}$ is ${\displaystyle b_0}$, and the cardinality of ${\displaystyle {\mathcal{D}}_{-}}$ is ${\displaystyle b_{-}}$, giving the number of positive and negative digits respectively, such that ${\displaystyle b=b_{+}+b_0+b_{-}}$.

Balanced form representations

Balanced form representations are representations where for every positive digit ${\displaystyle d_{+}}$, there exist a corresponding negative digit ${\displaystyle d_{-}}$ such that ${\displaystyle f_{\mathcal{D}}(d_{+})=-f_{\mathcal{D}}(d_{-})}$. It follows that ${\displaystyle b_{+}=b_{-}}$. For odd bases ${\displaystyle b}$, the used digits are ${\displaystyle -(b-1)/2}$ to ${\displaystyle (b-1)/2}$, and for even bases ${\displaystyle b}$, the used digits are ${\displaystyle -b/2}$ to ${\displaystyle b/2}$, but for even bases ${\displaystyle b}$, the digits ${\displaystyle -b/2}$ and ${\displaystyle b/2}$ may not be followed by an odd digit, the spacial case of ${\displaystyle b=2}$ is exactly the non-adjacent form. In balanced form, the negative digits ${\displaystyle d_{-}\in {\mathcal{D}}_{-}}$ are usually denoted as positive digits with a bar over the digit, as ${\displaystyle d_{-}={\overline{d}}_{+}}$ for ${\displaystyle d_{+}\in {\mathcal{D}}_{+}}$. For example, the digit set of balanced ternary would be ${\displaystyle {\mathcal{D}}_3=\{\overline{1},0,1\}}$ with ${\displaystyle f_{{\mathcal{D}}_3}(\overline{1})=-1}$, ${\displaystyle f_{{\mathcal{D}}_3}(0)=0}$, and ${\displaystyle f_{{\mathcal{D}}_3}(1)=1}$. This convention is adopted in finite fields of odd prime order ${\displaystyle q}$:

${\displaystyle {\mathbb{F}}_q=\{0,1,\overline{1}=-1,...d=\frac{q-1}{2},\overline{d}=\frac{1-q}{2}|q=0\}.}$

In the table below, use ${\displaystyle Z,Y,X,\dots }$ to represent ${\displaystyle -1,-2,-3,\dots }$

Dual signed-digit representation

Every digit set ${\displaystyle \mathcal{D}}$ has a dual digit set ${\displaystyle {\mathcal{D}}^{\mathrm{op}}}$ given by the inverse order of the digits with an isomorphism ${\displaystyle g:\mathcal{D}\to {\mathcal{D}}^{\mathrm{op}}}$ defined by ${\displaystyle -f_{\mathcal{D}}=g\circ f_{{\mathcal{D}}^{\mathrm{op}}}}$. As a result, for any signed-digit representations ${\displaystyle \mathcal{N}}$ of a number system ring ${\displaystyle N}$ constructed from ${\displaystyle \mathcal{D}}$ with valuation ${\displaystyle v_{\mathcal{D}}:\mathcal{N}\to N}$, there exists a dual signed-digit representations of ${\displaystyle N}$, ${\displaystyle {\mathcal{N}}^{\mathrm{op}}}$, constructed from ${\displaystyle {\mathcal{D}}^{\mathrm{op}}}$ with valuation ${\displaystyle v_{{\mathcal{D}}^{\mathrm{op}}}:{\mathcal{N}}^{\mathrm{op}}\to N}$, and an isomorphism ${\displaystyle h:\mathcal{N}\to {\mathcal{N}}^{\mathrm{op}}}$ defined by ${\displaystyle -v_{\mathcal{D}}=h\circ v_{{\mathcal{D}}^{\mathrm{op}}}}$, where ${\displaystyle -}$ is the additive inverse operator of ${\displaystyle N}$. The digit set for balanced form representations is self-dual.

For integers

Given the digit set ${\displaystyle \mathcal{D}}$ and function ${\displaystyle f:\mathcal{D}\to \mathbb{Z}}$ as defined above, let us define an integer endofunction ${\displaystyle T:\mathbb{Z}\to \mathbb{Z}}$ as the following:

${\displaystyle T(n)=\{\begin{array}{ll}\frac{n-f(d_i)}{b}& \text{if }n\equiv imodb,0\le i<b\end{array}}$

If the only periodic point of ${\displaystyle T}$ is the fixed point ${\displaystyle 0}$, then the set of all signed-digit representations of the integers ${\displaystyle \mathbb{Z}}$ using ${\displaystyle \mathcal{D}}$ is given by the Kleene plus ${\displaystyle {\mathcal{D}}^{+}}$, the set of all finite concatenated strings of digits ${\displaystyle d_n\dots d_0}$ with at least one digit, with ${\displaystyle n\in \mathbb{N}}$. Each signed-digit representation ${\displaystyle m\in {\mathcal{D}}^{+}}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^{+}\to \mathbb{Z}}$

${\displaystyle v_{\mathcal{D}}(m)=\sum _{i=0}^n{f}_{\mathcal{D}}(d_i)b^i}$.

Examples include balanced ternary with digits ${\displaystyle \mathcal{D}=\{\overline{1},0,1\}}$.

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

For decimal fractions

If the integers can be represented by the Kleene plus ${\displaystyle {\mathcal{D}}^{+}}$, then the set of all signed-digit representations of the decimal fractions, or ${\displaystyle b}$-adic rationals ${\displaystyle \mathbb{Z}[1\mathrm{\setminus }b]}$, is given by ${\displaystyle \mathcal{Q}={\mathcal{D}}^{+}\times \mathcal{P}\times {\mathcal{D}}^{\ast }}$, the Cartesian product of the Kleene plus ${\displaystyle {\mathcal{D}}^{+}}$, the set of all finite concatenated strings of digits ${\displaystyle d_n\dots d_0}$ with at least one digit, the singleton ${\displaystyle \mathcal{P}}$ consisting of the radix point (${\displaystyle .}$ or ${\displaystyle ,}$), and the Kleene star ${\displaystyle {\mathcal{D}}^{\ast }}$, the set of all finite concatenated strings of digits ${\displaystyle d_{-1}\dots d_{-m}}$, with ${\displaystyle m,n\in \mathbb{N}}$. Each signed-digit representation ${\displaystyle q\in \mathcal{Q}}$ has a valuation ${\displaystyle v_{\mathcal{D}}:\mathcal{Q}\to \mathbb{Z}[1\mathrm{\setminus }b]}$

${\displaystyle v_{\mathcal{D}}(q)=\sum _{i=-m}^n{f}_{\mathcal{D}}(d_i)b^i}$

For real numbers

If the integers can be represented by the Kleene plus ${\displaystyle {\mathcal{D}}^{+}}$, then the set of all signed-digit representations of the real numbers ${\displaystyle \mathbb{R}}$ is given by ${\displaystyle \mathcal{R}={\mathcal{D}}^{+}\times \mathcal{P}\times {\mathcal{D}}^{\mathbb{N}}}$, the Cartesian product of the Kleene plus ${\displaystyle {\mathcal{D}}^{+}}$, the set of all finite concatenated strings of digits ${\displaystyle d_n\dots d_0}$ with at least one digit, the singleton ${\displaystyle \mathcal{P}}$ consisting of the radix point (${\displaystyle .}$ or ${\displaystyle ,}$), and the Cantor space ${\displaystyle {\mathcal{D}}^{\mathbb{N}}}$, the set of all infinite concatenated strings of digits ${\displaystyle d_{-1}{d}_{-2}\dots }$, with ${\displaystyle n\in \mathbb{N}}$. Each signed-digit representation ${\displaystyle r\in \mathcal{R}}$ has a valuation ${\displaystyle v_{\mathcal{D}}:\mathcal{R}\to \mathbb{R}}$

${\displaystyle v_{\mathcal{D}}(r)=\sum _{i=-\mathrm{\infty }}^n{f}_{\mathcal{D}}(d_i)b^i}$.

The infinite series always converges to a finite real number.

For other number systems

All base-${\displaystyle b}$ numerals can be represented as a subset of ${\displaystyle {\mathcal{D}}^{\mathbb{Z}}}$, the set of all doubly infinite sequences of digits in ${\displaystyle \mathcal{D}}$, where ${\displaystyle \mathbb{Z}}$ is the set of integers, and the ring of base-${\displaystyle b}$ numerals is represented by the formal power series ring ${\displaystyle \mathbb{Z}[[b,b^{-1}]]}$, the doubly infinite series

${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}{a}_i{b}^i}$

where ${\displaystyle a_i\in \mathbb{Z}}$ for ${\displaystyle i\in \mathbb{Z}}$.

Integers modulo powers of b

The set of all signed-digit representations of the integers modulo ${\displaystyle b^n}$, ${\displaystyle \mathbb{Z}\mathrm{\setminus }{b}^n\mathbb{Z}}$ is given by the set ${\displaystyle {\mathcal{D}}^n}$, the set of all finite concatenated strings of digits ${\displaystyle d_{n-1}\dots d_0}$ of length ${\displaystyle n}$, with ${\displaystyle n\in \mathbb{N}}$. Each signed-digit representation ${\displaystyle m\in {\mathcal{D}}^n}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^n\to \mathbb{Z}/b^n\mathbb{Z}}$

${\displaystyle v_{\mathcal{D}}(m)\equiv \sum _{i=0}^{n-1}{f}_{\mathcal{D}}(d_i)b^i{modb}^n}$

Prüfer groups

A Prüfer group is the quotient group ${\displaystyle \mathbb{Z}(b^{\mathrm{\infty }})=\mathbb{Z}[1\mathrm{\setminus }b]/\mathbb{Z}}$ of the integers and the ${\displaystyle b}$-adic rationals. The set of all signed-digit representations of the Prüfer group is given by the Kleene star ${\displaystyle {\mathcal{D}}^{\ast }}$, the set of all finite concatenated strings of digits ${\displaystyle d_1\dots d_n}$, with ${\displaystyle n\in \mathbb{N}}$. Each signed-digit representation ${\displaystyle p\in {\mathcal{D}}^{\ast }}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^{\ast }\to \mathbb{Z}(b^{\mathrm{\infty }})}$

${\displaystyle v_{\mathcal{D}}(m)\equiv \sum _{i=1}^n{f}_{\mathcal{D}}(d_i)b^{-i}mod1}$

Circle group

The circle group is the quotient group ${\displaystyle \mathbb{T}=\mathbb{R}/\mathbb{Z}}$ of the integers and the real numbers. The set of all signed-digit representations of the circle group is given by the Cantor space ${\displaystyle {\mathcal{D}}^{\mathbb{N}}}$, the set of all right-infinite concatenated strings of digits ${\displaystyle d_1{d}_2\dots }$. Each signed-digit representation ${\displaystyle m\in {\mathcal{D}}^n}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^{\mathbb{N}}\to \mathbb{T}}$

${\displaystyle v_{\mathcal{D}}(m)\equiv \sum _{i=1}^{\mathrm{\infty }}{f}_{\mathcal{D}}(d_i)b^{-i}mod1}$

The infinite series always converges.

b-adic integers

The set of all signed-digit representations of the ${\displaystyle b}$-adic integers, ${\displaystyle {\mathbb{Z}}_b}$ is given by the Cantor space ${\displaystyle {\mathcal{D}}^{\mathbb{N}}}$, the set of all left-infinite concatenated strings of digits ${\displaystyle \dots d_1{d}_0}$. Each signed-digit representation ${\displaystyle m\in {\mathcal{D}}^n}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^{\mathbb{N}}\to {\mathbb{Z}}_b}$

${\displaystyle v_{\mathcal{D}}(m)=\sum _{i=0}^{\mathrm{\infty }}{f}_{\mathcal{D}}(d_i)b^i}$

b-adic solenoids

The set of all signed-digit representations of the ${\displaystyle b}$-adic solenoids, ${\displaystyle {\mathbb{T}}_b}$ is given by the Cantor space ${\displaystyle {\mathcal{D}}^{\mathbb{Z}}}$, the set of all doubly infinite concatenated strings of digits ${\displaystyle \dots d_1{d}_0{d}_{-1}\dots }$. Each signed-digit representation ${\displaystyle m\in {\mathcal{D}}^n}$ has a valuation ${\displaystyle v_{\mathcal{D}}:{\mathcal{D}}^{\mathbb{Z}}\to {\mathbb{T}}_b}$

${\displaystyle v_{\mathcal{D}}(m)=\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}{f}_{\mathcal{D}}(d_i)b^i}$

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, "un" or "unna" in Punjabi, "ekon" in 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"):

• 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, integers 18 and 19 had in practice neither spoken nor written form, even corresponding parts for "eight" or "nine –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:

• 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 of this is the scarce occurrence of these numbers written in such a 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:

• 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"

This phenomenon has no influence on written numerals, however; the Finnish use the standard Western-Arabic decimal notation.

Time keeping

In the English language it is common to refer to a time as, for example, "seven to three" (2:53, seven minutes before 3:00) in which 'to' performs the subtraction.

Other systems

There exist other signed-digit bases such that the base ${\displaystyle b\ne b_{+}+b_{-}+1}$. A notable examples of this is Booth encoding, which has a digit set ${\displaystyle \mathcal{D}=\{\overline{1},0,1\}}$ with ${\displaystyle b_{+}=1}$ and ${\displaystyle b_{-}=1}$, but which uses a base ${\displaystyle b=2<3=b_{+}+b_{-}+1}$. The standard binary numeral system would only use digits of value ${\displaystyle \{0,1\}}$.

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

${\displaystyle {0111}_{\mathcal{D}}=4+2+1=7}$

${\displaystyle 10\overline{1}{1}_{\mathcal{D}}=8-2+1=7}$

${\displaystyle 1\overline{1}{11}_{\mathcal{D}}=8-4+2+1=7}$

${\displaystyle 100{\overline{1}}_{\mathcal{D}}=8-1=7}$

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,

${\displaystyle \frac{2}{3}=0.{\overline{10}}_{\mathcal{D}}=1.{\overline{0\overline{1}}}_{\mathcal{D}}}$