GetWiki

{{Short description|Positional system with signed digits; the representation may not be unique}}{{Numeral systems}}{{distinguish|Signed number representations}}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.Dhananjay Phatak, I. Koren (1994) Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains 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).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. 434–42. In his book History of Mathematical Notations, Cajori titled the section "Negative numerals".BOOK, Cajori, Florian, Florian Cajori, A History of Mathematical Notations, 57, Dover Publications, 1993, 1928-1929, 978-0486677668,weblink registration, For completeness, ColsonJOURNAL, Colson, John, 1726, A Short Account of Negativo-Affirmative Arithmetick, by Mr. John Colson, F. R. S.,weblink Philosophical Transactions (1683-1775), 34, 161–173, 0260-7085, 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 SellingEduard Selling (1887) Eine neue Rechenmachine, pp. 15–18, Berlin 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.Rudolf Mehmke (1902) "Numerisches Rechen", §4 Beschränkung in den verwendeten Ziffern, Klein's encyclopedia, I-2, p. 944.

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. b is known as the radix or number base. mathcal{D} can be used for a signed-digit representation if it's associated with a unique function f_mathcal{D}:mathcal{D}rightarrowmathbb{Z} such that f_mathcal{D}(d_i) equiv i bmod b for all 0 leq i < b. This function, f_{mathcal{D}}, is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in 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. 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_{+}inmathcal{D}_{+} satisfy f_mathcal{D}(d_{+}) > 0, all digits d_{0}inmathcal{D}_{0} satisfy f_mathcal{D}(d_{0}) = 0 and all digits d_{-}inmathcal{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

{{See also|Balanced ternary}}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 otherwise d_{b/2} has to be the opposite of itself and hence 0, but 0ne frac b2. In balanced form, the negative digits d_{-}inmathcal{D}_{-} are usually denoted as positive digits with a bar over the digit, as d_{-} = bar{d}_{+} for d_{+}inmathcal{D}_{+}. For example, the digit set of balanced ternary would be mathcal{D}_{3} = lbracebar{1},0,1rbrace 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:BOOK, Projective Geometries Over Finite Fields, J. W. P., Hirschfeld, J. W. P. Hirschfeld, Oxford University Press, 1979, 8, 978-0-19-850295-1,

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}rightarrowmathcal{D}^operatorname{op} defined by -f_mathcal{D} = gcirc 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}rightarrowmathcal{N}^operatorname{op} defined by -v_mathcal{D} = hcirc 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}rightarrowmathbb{Z} as defined above, let us define an integer endofunction T:mathbb{Z}rightarrowmathbb{Z} as the following: begin{cases}frac{n - f(d_i)}{b} &text{if } n equiv i bmod b, 0 leq i < bend{cases}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 ninmathbb{N}. Each signed-digit representation m in mathcal{D}^+ has a valuation v_mathcal{D}:mathcal{D}^+rightarrowmathbb{Z} Examples include balanced ternary with digits mathcal{D} = lbrace bar{1}, 0, 1rbrace. 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, 1rbrace 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}[1backslash b], is given by mathcal{Q} = mathcal{D}^+timesmathcal{P}timesmathcal{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,ninmathbb{N}. Each signed-digit representation q in mathcal{Q} has a valuation v_mathcal{D}:mathcal{Q}rightarrowmathbb{Z}[1backslash b]

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 ninmathbb{N}. Each signed-digit representation r in mathcal{R} has a valuation v_mathcal{D}:mathcal{R}rightarrowmathbb{R} 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 where a_iinmathbb{Z} for iinmathbb{Z}.

Integers modulo powers of {{math|b}}

The set of all signed-digit representations of the integers modulo b^n, mathbb{Z}backslash b^nmathbb{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 ninmathbb{N}. Each signed-digit representation m in mathcal{D}^n has a valuation v_mathcal{D}:mathcal{D}^nrightarrowmathbb{Z}/b^nmathbb{Z}

Prüfer groups

A Prüfer group is the quotient group mathbb{Z}(b^infty) = mathbb{Z}[1backslash 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 ninmathbb{N}. Each signed-digit representation p in mathcal{D}^* has a valuation v_mathcal{D}:mathcal{D}^*rightarrowmathbb{Z}(b^infty)

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}rightarrowmathbb{T} The infinite series always converges.

{{math|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}rightarrowmathbb{Z}_{b}

{{math|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}rightarrowmathbb{T}_{b}

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"):Punjabi numbers from Quizlet

• 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,J. Matthew Harrington (2016) Synopsis of Ancient Latin Grammar 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:{{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}}

• 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:WEB, Kielitoimiston sanakirja,weblink 2024-04-07, www.kielitoimistonsanakirja.fi,

• 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 b neq b_{+} + b_{-} + 1. A notable examples of this is Booth encoding, which has a digit set mathcal{D} = lbracebar{1},0,1rbrace 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 lbrace0,1rbrace.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

{{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 "Non-speculative Decimal Signed Digit Adder" from Department of Electrical and Computer Engineering, University of Saskatchewan.

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