In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signeded digitss 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

be a finite set of numerical digits with cardinality, then the positional number system is trivial and only represents the trivial ring is known as the radix or number base can be used for a signed-digit representation if it's associated with a unique function 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.

can be partitioned.

Balanced form representations

. For odd, and for even is exactly the non-adjacent form. For example, the digit set of balanced ternary. This convention is adopted in finite fields of odd prime:

Dual signed-digit representation

has a dual given by the inverse order of the digits with an isomorphism of a number system ring with valuation with valuation. The digit set for balanced form representations is self-dual.

For integers

as defined above, let us define an integer endofunction as the following:

If the only periodic point is the fixed point, then the set of all signed-digit representations of the integers is given by the Kleene plus, the set of all finite concatenated has a valuation

1. .

Examples include balanced ternary.

Otherwise, if there exist a non-zero periodic point. Examples include the standard decimal numeral system, which requires an infinite number of the digit to represent the additive inverse.

For decimal fractions

If the integers can be represented by the Kleene plus, then the set of all signed-digit representations of the decimal fractions, or b-adic rationals, the Cartesian product of the Kleene plus, the set of all finite concatenated with at least one digit, the singleton consisting of the radix point), and the Kleene star, the set of all finite concatenated has a valuation

For real numbers

If the integers can be represented by the Kleene plus, then the set of all signed-digit representations of the real numbers, the Cartesian product of the Kleene plus, the set of all finite concatenated with at least one digit, the singleton consisting of the radix point), and the Cantor space, the set of all infinite concatenated has a valuation

1. .

The infinite series always converges to a finite real number.

For other number systems

, the set of all doubly infinite sequences is the set of integers, and the ring numerals is represented by the formal power series ring, the doubly infinite series

.

Integers modulo powers of b

The set of all signed-digit representations of the b^n, the set of all finite concatenated has a valuation

Prüfer groups

A Prüfer group is the quotient group-adic rationals. The set of all signed-digit representations of the Prüfer group is given by the Kleene star, the set of all finite concatenated has a valuation

Circle group

The circle group of the integers and the real numbers. The set of all signed-digit representations of the circle group is given by the Cantor space has a valuation

The infinite series always converges.

b-adic integers

The set of all signed-digit representations of the b-adic integers is given by the Cantor space has a valuation

b-adic solenoids

The set of all signed-digit representations of the b-adic solenoids is given by the Cantor space, the set of all doubly infinite has a valuation

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

. A notable examples of this is Booth encoding. The standard binary numeral system.

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

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,

See also

• Balanced ternary

• Negative base

• Redundant binary representation

Notes and references

• J. P. Balantine (1925) "A Digit for Negative One", American Mathematical Monthly 32:302.

• Lui Han, Dongdong Chen, Seok-Bum Ko, Khan A. Wahid "Non-speculative Decimal Signed Digit Adder" from Department of Electrical and Computer Engineering, University of Saskatchewan.