Signed-digit representation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

Denoting the positional notation number base as , every integer can be written uniquely as

where each digit is an integer such that . given that is the minimum digit value and is the maximum digit value, where the leading digit unless , and where the base . Negative-integer digits are typically represented with a bar over the digit, i.e. .

Balanced form[edit]

Balanced form representations are representations where , 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 , is always an odd number.

For example, consider the ternary numeral system with only three digits. In standard ternary, the digits are ; however, the balanced form of ternary, balanced ternary, uses digits . This convention is adopted in finite fields of odd prime order :[2]

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

Signed-digit decimal[edit]

Signed-digits are commonly associated with the decimal number system. The following table displays the signed-digit representations of the integers for base .

Decimal for minimum digit value
(Unsigned decimal)

Table[edit]

The following table displays the set of digits for each signed-digit representations for and .

Set of digits for and
0 1 2 3 4 5
0
1
2
3
4
5

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 , the representation can only represent non-negative integers without the use of a sign, and when , the representation can only represent non-positive integers without the use of a sign. When both and , only zero can be represented, yielding the trivial ring.

Non-uniqueness of rationals[edit]

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

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.

Additional properties[edit]

For any natural number , the base- integers, when represented with both positive and negative digits, is the direct limit of the groups with the index set being the natural numbers with the usual order, and the homomorphisms induced by the modulo 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 -adic integers, which are the inverse limit of the groups with the index set being the natural numbers with the usual order, and the homomorphisms induced by the modulo operation.

For any natural number , the fractional part of a base- decimal fraction is known as the Prüfer -group, and is the direct limit of the groups with the index set being the natural numbers with the usual order, and the homomorphisms induced by multiplication by . The direct sum of the Prüfer -group and the group of base- integers is the group of base- decimal fractions themselves, otherwise known as the -adic rationals.

The inverse limit of the groups , with the index set being the natural numbers with the usual order, and the homomorphisms induced by multiplication by , is the base- representation of the circle group, and the direct sum of the base- circle group and the base- integers is the base- 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 , the base integers could be thought as the Prüfer -group endowed with the -adic norm instead of the Euclidean norm. A similar phenomenon occurs with the -adic integers, which are the base- circle group endowed with the -adic norm instead of the Euclidean norm. The -adic rationals endowed with the -adic norm are isomorphic to the -adic rationals themselves endowed with the Euclidean norm.

History[edit]

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[edit]

There exist other signed-digit bases such that the base . A notable examples of this is Booth encoding, which has and , with digits of value , but which uses a base . The standard binary numeral system would only use digits of value .

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,

In written and spoken language[edit]

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.

See also[edit]

Notes and references[edit]

  1. ^ Dhananjay Phatak, I. Koren (1994) Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains
  2. ^ Hirschfeld, J. W. P. (1979). Projective Geometries Over Finite Fields. Oxford University Press. p. 8. ISBN 978-0-19-850295-1.
  3. ^ Augustin-Louis Cauchy (16 Nov 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.
  4. ^ Cajori, Florian (1993) [1928-1929]. A History of Mathematical Notations. Dover Publications. p. 57. ISBN 978-0486677668.
  5. ^ John Colson (1726) "A Short Account of Negativo-Affirmativo Arithmetik", Philosophical Transactions of the Royal Society 34:161–173. Available as Early Journal Content from JSTOR
  6. ^ Eduard Selling (1887) Eine neue Rechenmachine, pp. 15–18, Berlin
  7. ^ Rudolf Mehmke (1902) "Numerisches Rechen", §4 Beschränkung in den verwendeten Ziffern, Klein's encyclopedia, I-2, p. 944.
  8. ^ Punjabi numbers from Quizlet