Signed-digit representation

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

In mathematical notation for numbers, signed-digit representation indicates that each digit is associated with a sign, positive or negative.

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).

Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries.[1] In the binary numeral system one special case of signed-digit representation is the non-adjacent form which can offer speed benefits with minimal space overhead.

Balanced form[edit]

In balanced form, the digits are drawn from a range -k to (b-1) - k, where typically k = \left\lfloor\frac{b}{2}\right\rfloor. For balanced forms, odd base numbers are advantageous. With an odd base number, truncation and rounding become the same operation, and all the digits except 0 are used in both positive and negative form.

A notable example is balanced ternary, where the base is b=3, and the numerals have the values −1, 0 and +1 (rather than 0, 1, and 2 as in the standard ternary numeral system). Balanced ternary uses the minimum number of digits in a balanced form. Balanced decimal uses digits from −5 to +4. Balanced base nine, with digits from −4 to +4 provides the advantages of an odd-base balanced form with a similar number of digits, and is easy to convert to and from balanced ternary.

Other notable examples include Booth encoding and non-adjacent form, both of which use a base of b=2, and both of which use numerals with the values −1, 0, and +1 (rather than 0 and 1 as in the standard binary numeral system).

Non-unique representations[edit]

Note that signed-digit representation is not necessarily unique. For instance:

(0 1 1 1)2 = 4 + 2 + 1 = 7
(1 0 −1 1)2 = 8 − 2 + 1 = 7
(1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7
(1 0 0 −1)2 = 8 − 1 = 7

The non-adjacent form does guarantee a unique representation for every integer value, as do balanced forms.

When representations are extended to fractional numbers, uniqueness is lost for non-adjacent and balanced forms; for example,

(0 . (1 0) …)NAF = 23 = (1 . (0 −1) …)NAF [clarification needed]

and

(0 . 4 4 4 …)(10bal) = 49 = (1 . -5 -5 -5 …)(10bal)

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. (Indeed, this works with any integral-base system.)

Negative numerals[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.[2] 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.

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".[3] Eduard Selling[4] 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. 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.

See also[edit]

Notes and references[edit]

  1. ^ Dhananjay Phatak, I. Koren, Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains, 1994, [1]
  2. ^ Punjabi numbers from Quizlet
  3. ^ Cajori, Florian (1993) [1928-1929]. A History of Mathematical Notations. Dover Publications. p. 57. ISBN 0486677664. 
  4. ^ Eduard Selling (1887) Eine neue Rechenmachine, pp. 15–18, Berlin
  5. ^ John Colson (1726) "A Short Account of Negativo-Affirmativo Arithmetik", Philosophical Transactions of the Royal Society 34:161–73. Available as Early Journal Content from JSTOR