# Signed-digit representation

Numeral systems |
---|

Hindu–Arabic numeral system |

East Asian |

Alphabetic |

Former |

Positional systems by base |

Non-standard positional numeral systems |

List of numeral systems |

In mathematical notation for numbers, **signed-digit representation** is a positional system with signed digits; the representation may not be unique.

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

## Contents

## Balanced form[edit]

Consider the ternary numeral system with only three digits {0, 1, 2}, it is often used in the balanced ternary form using digits {–1, 0, 1}. This convention is adopted in finite fields of odd prime order *q*:^{[2]}

In positional notation with base *b*, balanced form signed digits may also be used, the digits are drawn from a range −*k* to (*b* − 1) − *k*, where typically

- .

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.

*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-uniqueness[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 (NAF) 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, consider the following repeating binary numbers in NAF,

- (0 . 1 0 1 0 1 0 …)
_{2}= 2/3 = (1 . 0 −1 0 −1 0 −1 …)_{2}

and the balanced form repeating decimals

- (0 . 4 4 4 …)
_{10}= 4/9 = (1 . −5 −5 −5 …)_{10}

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

## 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*,^{[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 also[edit]

## Notes and references[edit]

**^**Dhananjay Phatak, I. Koren,**Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains**, 1994, [1]**^**Hirschfeld, J. W. P. (1979).*Projective Geometries Over Finite Fields*. Oxford University Press. p. 8. ISBN 978-0-19-850295-1.**^**Punjabi numbers from Quizlet**^**Cajori, Florian (1993) [1928-1929].*A History of Mathematical Notations*. Dover Publications. p. 57. ISBN 0486677664.**^**Eduard Selling (1887)*Eine neue Rechenmachine*, pp. 15–18, Berlin**^**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

- J. P. Balantine (1925) "A Digit for Negative One", American Mathematical Monthly 32:302.
- 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. - 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.
- Rudolf Mehmke (1902) "Numerisches Rechen", §4 Beschränkung in den verwendeten Ziffern, Klein's encyclopedia, I-2, p. 944.