# 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 ${\mathcal {D}}$  be a finite set of numerical digits with cardinality $b>1$  (If $b\leq 1$ , then the positional number system is trivial and only represents the trivial ring), with each digit denoted as $d_{i}$  for $0\leq i . $b$  is known as the radix or number base. ${\mathcal {D}}$  can be used for a signed-digit representation if there exists a unique function $f_{\mathcal {D}}:{\mathcal {D}}\rightarrow \mathbb {Z}$  such that $f_{\mathcal {D}}(d_{i})\equiv i{\bmod {b}}$ .

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

#### Balanced form representations

Balanced form representations are representations where for every positive digit $d_{+}$ , there exist a corresponding negative digit $d_{-}$  such that $f_{\mathcal {D}}(d_{+})=-f_{\mathcal {D}}(d_{-})$ . It follows that $b_{+}=b_{-}$ . Only odd bases can have balanced form representations, as when $b_{+}=b_{-}$ , $b=b_{+}+b_{-}+1$  is always an odd number. In balanced form, the negative digits $d_{-}\in {\mathcal {D}}_{-}$  are usually denoted as positive digits with a bar over the digit, as $d_{-}={\bar {d}}_{+}$  for $d_{+}\in {\mathcal {D}}_{+}$ . For example, the digit set of balanced ternary would be ${\mathcal {D}}_{3}=\lbrace {\bar {1}},0,1\rbrace$  with $f_{{\mathcal {D}}_{3}}({\bar {1}})=-1$ , $f_{{\mathcal {D}}_{3}}(0)=0$ , and $f_{{\mathcal {D}}_{3}}(1)=1$ . This convention is adopted in finite fields of odd prime order $q$ :

$\mathbb {F} _{q}=\lbrace 0,1,{\bar {1}}=-1,...d={\frac {q-1}{2}},\ {\bar {d}}={\frac {1-q}{2}}\ |\ q=0\rbrace .$

#### Dual signed-digit representation

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

### For integers

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

$T(n)={\begin{cases}{\frac {n-f(d_{i})}{b}}&{\text{if }}n\equiv i{\bmod {b}},0\leq i

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

$v_{\mathcal {D}}(m)=\sum _{i=0}^{n}f_{\mathcal {D}}(d_{i})b^{i}$ .

Examples include balanced ternary with digits ${\mathcal {D}}=\lbrace {\bar {1}},0,1\rbrace$ .

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

### For decimal fractions

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

$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 ${\mathcal {D}}^{+}$ , then the set of all signed-digit representations of the real numbers $\mathbb {R}$  is given by ${\mathcal {R}}={\mathcal {D}}^{+}\times {\mathcal {P}}\times {\mathcal {D}}^{\mathbb {N} }$ , the Cartesian product of the Kleene plus ${\mathcal {D}}^{+}$ , the set of all finite concatenated strings of digits $d_{n}\ldots d_{0}$  with at least one digit, the singleton ${\mathcal {P}}$  consisting of the radix point ($.$  or $,$ ), and the Cantor space ${\mathcal {D}}^{\mathbb {N} }$ , the set of all infinite concatenated strings of digits $d_{-1}d_{-2}\ldots$ , with $n\in \mathbb {N}$ . Each signed-digit representation $r\in {\mathcal {R}}$  has a valuation $v_{\mathcal {D}}:{\mathcal {R}}\rightarrow \mathbb {R}$

$v_{\mathcal {D}}(r)=\sum _{i=-\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-$b$  numerals can be represented as a subset of ${\mathcal {D}}^{\mathbb {Z} }$ , the set of all doubly infinite sequences of digits in ${\mathcal {D}}$ , where $\mathbb {Z}$  is the set of integers, and the ring of base-$b$  numerals is represented by the formal power series ring $\mathbb {Z} [[b,b^{-1}]]$ , the doubly infinite series

$\sum _{i=-\infty }^{\infty }a_{i}b^{i}$

where $a_{i}\in \mathbb {Z}$  for $i\in \mathbb {Z}$ .

#### Integers modulo $b^{n}$ The set of all signed-digit representations of the integers modulo $b^{n}$ , $\mathbb {Z} \backslash b^{n}\mathbb {Z}$  is given by the set ${\mathcal {D}}^{n}$ , the set of all finite concatenated strings of digits $d_{n-1}\ldots d_{0}$  of length $n$ , with $n\in \mathbb {N}$ . Each signed-digit representation $m\in {\mathcal {D}}^{n}$  has a valuation $v_{\mathcal {D}}:{\mathcal {D}}^{n}\rightarrow \mathbb {Z} /b^{n}\mathbb {Z}$

$v_{\mathcal {D}}(m)\equiv \sum _{i=0}^{n-1}f_{\mathcal {D}}(d_{i})b^{i}{\bmod {b}}^{n}$

#### Prüfer groups

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

$v_{\mathcal {D}}(m)\equiv \sum _{i=1}^{n}f_{\mathcal {D}}(d_{i})b^{-i}{\bmod {1}}$

#### Circle group

The circle group is the quotient group $\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 ${\mathcal {D}}^{\mathbb {N} }$ , the set of all right-infinite concatenated strings of digits $d_{1}d_{2}\ldots$ . Each signed-digit representation $m\in {\mathcal {D}}^{n}$  has a valuation $v_{\mathcal {D}}:{\mathcal {D}}^{\mathbb {N} }\rightarrow \mathbb {T}$

$v_{\mathcal {D}}(m)\equiv \sum _{i=1}^{\infty }f_{\mathcal {D}}(d_{i})b^{-i}{\bmod {1}}$

The infinite series always converges.

#### $b$ -adic integers

The set of all signed-digit representations of the $b$ -adic integers, $\mathbb {Z} _{b}$  is given by the Cantor space ${\mathcal {D}}^{\mathbb {N} }$ , the set of all left-infinite concatenated strings of digits $\ldots d_{1}d_{0}$ . Each signed-digit representation $m\in {\mathcal {D}}^{n}$  has a valuation $v_{\mathcal {D}}:{\mathcal {D}}^{\mathbb {N} }\rightarrow \mathbb {Z} _{b}$

$v_{\mathcal {D}}(m)=\sum _{i=0}^{\infty }f_{\mathcal {D}}(d_{i})b^{i}$

#### $b$ -adic solenoids

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

$v_{\mathcal {D}}(m)=\sum _{i=-\infty }^{\infty }f_{\mathcal {D}}(d_{i})b^{i}$

## 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:

• 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

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 $b\neq b_{+}+b_{-}+1$ . A notable examples of this is Booth encoding, which has a digit set ${\mathcal {D}}=\lbrace {\bar {1}},0,1\rbrace$  with $b_{+}=1$  and $b_{-}=1$ , but which uses a base $b=2<3=b_{+}+b_{-}+1$ . The standard binary numeral system would only use digits of value $\lbrace 0,1\rbrace$ .

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

$0111_{\mathcal {D}}=4+2+1=7$
$10{\bar {1}}1_{\mathcal {D}}=8-2+1=7$
$1{\bar {1}}11_{\mathcal {D}}=8-4+2+1=7$
$100{\bar {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,

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