Open main menu

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.

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


Notation and useEdit

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 formEdit

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 decimalEdit

The following table displays the signed-digit representations of the integers   for base  .

Decimal for minimum digit value  
  (Unsigned decimal)                  
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   

TableEdit

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            

The table itself is skew-symmetric. 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 rationalsEdit

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.

OtherEdit

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 languageEdit

The oral and written forms of numbers in the Punjabi language use a form of a negative numeral one written as una or un.[3] 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, e.g., 'seven til three', 'til' performing the negation. 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".[4] Eduard Selling[5] 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[6] 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 alsoEdit

Notes and referencesEdit

  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. ^ Hirschfeld, J. W. P. (1979). Projective Geometries Over Finite Fields. Oxford University Press. p. 8. ISBN 978-0-19-850295-1.
  3. ^ Punjabi numbers from Quizlet
  4. ^ Cajori, Florian (1993) [1928-1929]. A History of Mathematical Notations. Dover Publications. p. 57. ISBN 978-0486677668.
  5. ^ Eduard Selling (1887) Eine neue Rechenmachine, pp. 15–18, Berlin
  6. ^ 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