Signed-digit representation

In mathematical notation for numbers, signed-digit representation is a positional system with signed digits.

Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries.[1] 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.

Notation and use

Denoting the positional notation number base as ${\displaystyle b}$, every integer ${\displaystyle a}$ can be written uniquely as

${\displaystyle a=\sum _{i=0}^{n}d_{i}(b)^{i}}$

where each digit ${\displaystyle d_{k}}$ is an integer such that ${\displaystyle -\alpha \leq d_{k}\leq \beta }$. given that ${\displaystyle -\alpha \leq 0}$ is the minimum digit value and ${\displaystyle \beta \geq 0}$ is the maximum digit value, where the leading digit ${\displaystyle d_{n}>0}$ unless ${\displaystyle n=0}$, and where the base ${\displaystyle b=\alpha +\beta +1}$. Negative-integer digits are typically represented with a bar over the digit, i.e. ${\displaystyle -\alpha ={\bar {\alpha }}}$.

Balanced form

Balanced form representations are representations where ${\displaystyle \alpha =\beta }$, or equivalently, where there are an equal number of negative and positive digits in the set of digits for the representation. Only odd bases can have balanced form representations, as when ${\displaystyle \alpha =\beta }$, ${\displaystyle b=\alpha +\beta +1}$ is always an odd number.

For example, consider the ternary numeral system with only three digits. In standard ternary, the digits are ${\displaystyle \lbrace 0,1,2\rbrace }$; however, the balanced form of ternary, balanced ternary, uses digits ${\displaystyle \lbrace {\bar {1}},0,1\rbrace }$. This convention is adopted in finite fields of odd prime order ${\displaystyle q}$:[2]

${\displaystyle GF(q)=\lbrace 0,1,{\bar {1}}=-1,...\beta ={\frac {q-1}{2}},\ {\bar {\beta }}={\frac {1-q}{2}}\ |\ q=0\rbrace .}$

In balanced form, truncation and rounding become the same operation.

Signed-digit decimal

Signed-digits are commonly associated with the decimal number system. The following table displays the signed-digit representations of the integers ${\displaystyle -10\leq n\leq 10}$ for base ${\displaystyle b=10=\alpha +\beta +1}$.

Decimal for minimum digit value ${\displaystyle 0\leq \alpha
${\displaystyle \alpha =0}$ (Unsigned decimal) ${\displaystyle \alpha =1}$ ${\displaystyle \alpha =2}$ ${\displaystyle \alpha =3}$ ${\displaystyle \alpha =4}$ ${\displaystyle \alpha =5}$ ${\displaystyle \alpha =6}$ ${\displaystyle \alpha =7}$ ${\displaystyle \alpha =8}$ ${\displaystyle \alpha =9}$
${\displaystyle -10}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$ ${\displaystyle {\bar {1}}0}$
${\displaystyle -9}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {1}}1}$ ${\displaystyle {\bar {9}}}$
${\displaystyle -8}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {1}}2}$ ${\displaystyle {\bar {8}}}$ ${\displaystyle {\bar {8}}}$
${\displaystyle -7}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {1}}3}$ ${\displaystyle {\bar {7}}}$ ${\displaystyle {\bar {7}}}$ ${\displaystyle {\bar {7}}}$
${\displaystyle -6}$ ${\displaystyle {\bar {1}}4}$ ${\displaystyle {\bar {1}}4}$ ${\displaystyle {\bar {1}}4}$ ${\displaystyle {\bar {1}}4}$ ${\displaystyle {\bar {1}}4}$ ${\displaystyle {\bar {6}}}$ ${\displaystyle {\bar {6}}}$ ${\displaystyle {\bar {6}}}$ ${\displaystyle {\bar {6}}}$
${\displaystyle -5}$ ${\displaystyle {\bar {1}}5}$ ${\displaystyle {\bar {1}}5}$ ${\displaystyle {\bar {1}}5}$ ${\displaystyle {\bar {1}}5}$ ${\displaystyle {\bar {5}}}$ ${\displaystyle {\bar {5}}}$ ${\displaystyle {\bar {5}}}$ ${\displaystyle {\bar {5}}}$ ${\displaystyle {\bar {5}}}$
${\displaystyle -4}$ ${\displaystyle {\bar {1}}6}$ ${\displaystyle {\bar {1}}6}$ ${\displaystyle {\bar {1}}6}$ ${\displaystyle {\bar {4}}}$ ${\displaystyle {\bar {4}}}$ ${\displaystyle {\bar {4}}}$ ${\displaystyle {\bar {4}}}$ ${\displaystyle {\bar {4}}}$ ${\displaystyle {\bar {4}}}$
${\displaystyle -3}$ ${\displaystyle {\bar {1}}7}$ ${\displaystyle {\bar {1}}7}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$ ${\displaystyle {\bar {3}}}$
${\displaystyle -2}$ ${\displaystyle {\bar {1}}8}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {2}}}$
${\displaystyle -1}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$
${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$
${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle -{\bar {1}}}$
${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 1{\bar {8}}}$ ${\displaystyle -{\bar {2}}}$
${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 3}$ ${\displaystyle 1{\bar {7}}}$ ${\displaystyle 1{\bar {7}}}$ ${\displaystyle -{\bar {3}}}$
${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 4}$ ${\displaystyle 1{\bar {6}}}$ ${\displaystyle 1{\bar {6}}}$ ${\displaystyle 1{\bar {6}}}$ ${\displaystyle -{\bar {4}}}$
${\displaystyle 5}$ ${\displaystyle 5}$ ${\displaystyle 5}$ ${\displaystyle 5}$ ${\displaystyle 5}$ ${\displaystyle 1{\bar {5}}}$ ${\displaystyle 1{\bar {5}}}$ ${\displaystyle 1{\bar {5}}}$ ${\displaystyle 1{\bar {5}}}$ ${\displaystyle -{\bar {5}}}$
${\displaystyle 6}$ ${\displaystyle 6}$ ${\displaystyle 6}$ ${\displaystyle 6}$ ${\displaystyle 1{\bar {4}}}$ ${\displaystyle 1{\bar {4}}}$ ${\displaystyle 1{\bar {4}}}$ ${\displaystyle 1{\bar {4}}}$ ${\displaystyle 1{\bar {4}}}$ ${\displaystyle -{\bar {6}}}$
${\displaystyle 7}$ ${\displaystyle 7}$ ${\displaystyle 7}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle 1{\bar {3}}}$ ${\displaystyle -{\bar {7}}}$
${\displaystyle 8}$ ${\displaystyle 8}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle 1{\bar {2}}}$ ${\displaystyle -{\bar {8}}}$
${\displaystyle 9}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle 1{\bar {1}}}$ ${\displaystyle -{\bar {9}}}$
${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle 10}$ ${\displaystyle -{\bar {1}}0}$

Table

The following table displays the set of digits for each signed-digit representations for ${\displaystyle \alpha \leq 5}$ and ${\displaystyle \beta \leq 5}$.

Set of digits for ${\displaystyle \alpha \leq 5}$ and ${\displaystyle \beta \leq 5}$
${\displaystyle \alpha ,\beta }$ 0 1 2 3 4 5
0 ${\displaystyle \lbrace 0\rbrace }$ ${\displaystyle \lbrace 0,1\rbrace }$ ${\displaystyle \lbrace 0,1,2\rbrace }$ ${\displaystyle \lbrace 0,1,2,3\rbrace }$ ${\displaystyle \lbrace 0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace 0,1,2,3,4,5\rbrace }$
1 ${\displaystyle \lbrace {\bar {1}},0\rbrace }$ ${\displaystyle \lbrace {\bar {1}},0,1\rbrace }$ ${\displaystyle \lbrace {\bar {1}},0,1,2\rbrace }$ ${\displaystyle \lbrace {\bar {1}},0,1,2,3\rbrace }$ ${\displaystyle \lbrace {\bar {1}},0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace {\bar {1}},0,1,2,3,4,5\rbrace }$
2 ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0\rbrace }$ ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0,1\rbrace }$ ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0,1,2\rbrace }$ ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0,1,2,3\rbrace }$ ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace {\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace }$
3 ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0\rbrace }$ ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace }$ ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace }$ ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace }$ ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace }$
4 ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0\rbrace }$ ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace }$ ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace }$ ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace }$ ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace }$
5 ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0\rbrace }$ ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace }$ ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace }$ ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace }$ ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace }$ ${\displaystyle \lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace }$

Considered as a matrix, the table itself is a skew-symmetric matrix. The representations down the diagonal are the balanced form signed-digit representations, while the representations on either side of the diagonal are isomorphic to its counterpart on the other side of the diagonal by negation, where positive numbers on one side correspond to negative numbers on the other, and vice versa. When ${\displaystyle \alpha =0}$, the representation can only represent non-negative integers without the use of a sign, and when ${\displaystyle \beta =0}$, the representation can only represent non-positive integers without the use of a sign. When both ${\displaystyle \alpha =0}$ and ${\displaystyle \beta =0}$, only zero can be represented, yielding the trivial ring.

Non-uniqueness of rationals

Just as with unsigned positional number systems, when the representations are extended to rational numbers, uniqueness is lost. For example, consider signed-digit decimal with ${\displaystyle \alpha =5}$

${\displaystyle {(0.4444\ldots )}_{10}={\frac {4}{9}}={(1.{\bar {5}}{\bar {5}}{\bar {5}}{\bar {5}}\ldots )}_{10}}$

Such examples can be shown to exist by considering the greatest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal.

For any natural number ${\displaystyle b}$, the base-${\displaystyle b}$ integers, when represented with both positive and negative digits, is the direct limit of the groups ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} }$ with the index set being the natural numbers with the usual order, and the homomorphisms ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} \rightarrow \mathbb {Z} /b^{n+1}\mathbb {Z} }$ induced by the modulo ${\displaystyle b}$ operation. If there are either no negative or no positive digits in the base, then attempting the direct limit does not yield a group, but only a monoid, consisting only of the non-negative or non-positive integers respectively, as the additive inverse cannot be represented by a finite number of non-zero digits without a negation operator and as radix complements require an infinite number of non-zero digits. When there are neither negative nor positive digits, the only digit left is the digit representing zero, yielding a direct system of trivial groups and a direct limit that is still the trivial group, not the group of integers. Hence, by the definition of the direct limit of groups, it is required that the digit representation has to contain both positive and negative digits for the system to be isomorphic to the integers.

Commonly used in number theory are the ${\displaystyle b}$-adic integers, which are the inverse limit of the groups ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} }$ with the index set being the natural numbers with the usual order, and the homomorphisms ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} \rightarrow \mathbb {Z} /b^{n+1}\mathbb {Z} }$ induced by the modulo ${\displaystyle b}$ operation.

For any natural number ${\displaystyle b}$, the fractional part of a base-${\displaystyle b}$ decimal fraction is known as the Prüfer ${\displaystyle b}$-group, and is the direct limit of the groups ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} }$ with the index set being the natural numbers with the usual order, and the homomorphisms ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} \rightarrow \mathbb {Z} /b^{n+1}\mathbb {Z} }$ induced by multiplication by ${\displaystyle b}$. The direct sum of the Prüfer ${\displaystyle b}$-group and the group of base-${\displaystyle b}$ integers is the group of base-${\displaystyle b}$ decimal fractions themselves, otherwise known as the ${\displaystyle b}$-adic rationals.

The inverse limit of the groups ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} }$, with the index set being the natural numbers with the usual order, and the homomorphisms ${\displaystyle \mathbb {Z} /b^{n}\mathbb {Z} \rightarrow \mathbb {Z} /b^{n+1}\mathbb {Z} }$ induced by multiplication by ${\displaystyle b}$, is the base-${\displaystyle b}$ representation of the circle group, and the direct sum of the base-${\displaystyle b}$ circle group and the base-${\displaystyle b}$ integers is the base-${\displaystyle b}$ representation of the real numbers. This provides a formalisation of the standard construction of the real numbers taught in secondary school (cf. 0.999...#Infinite_decimal_representation) for signed-digit representations, and is similar to the construction of the reals by Cauchy sequences.

For a prime number ${\displaystyle p}$, the base ${\displaystyle p}$ integers could be thought as the Prüfer ${\displaystyle p}$-group endowed with the ${\displaystyle p}$-adic norm instead of the Euclidean norm. A similar phenomenon occurs with the ${\displaystyle p}$-adic integers, which are the base-${\displaystyle p}$ circle group endowed with the ${\displaystyle p}$-adic norm instead of the Euclidean norm. The ${\displaystyle p}$-adic rationals endowed with the ${\displaystyle p}$-adic norm are isomorphic to the ${\displaystyle p}$-adic rationals themselves endowed with the Euclidean norm.

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).[3] In his book History of Mathematical Notations, Cajori titled the section "Negative numerals".[4] For completeness, Colson[5] 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[6] 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.[7]

Other systems

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

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

${\displaystyle 0111_{2}=4+2+1=7}$
${\displaystyle 10{\bar {1}}1_{2}=8-2+1=7}$
${\displaystyle 1{\bar {1}}11_{2}=8-4+2+1=7}$
${\displaystyle 100{\bar {1}}_{2}=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 (0.101010\ldots )_{2}={\frac {2}{3}}=(1.0{\bar {1}}0{\bar {1}}0{\bar {1}}\ldots )_{2}}$

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.[8] 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.