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

## Balanced form

In balanced form, 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.

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-uniqueness

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

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.

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

## Notes and references

- ↑ Dhananjay Phatak, I. Koren,
**Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains**, 1994, - ↑ 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.