In
mathematical notation
Mathematical notation consists of using symbols for representing operations, unspecified numbers, relations and any other mathematical objects, and assembling them into expressions and formulas. Mathematical notation is widely used in mathematic ...
for
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
s, a signed-digit representation is a
positional numeral system
Positional notation (or place-value notation, or positional numeral system) usually denotes the extension to any radix, base of the Hindu–Arabic numeral system (or decimal, decimal system). More generally, a positional system is a numeral syste ...
with a set of
sign
A sign is an object, quality, event, or entity whose presence or occurrence indicates the probable presence or occurrence of something else. A natural sign bears a causal relation to its object—for instance, thunder is a sign of storm, or me ...
ed
digits used to
encode
The Encyclopedia of DNA Elements (ENCODE) is a public research project which aims to identify functional elements in the human genome.
ENCODE also supports further biomedical research by "generating community resources of genomics data, software ...
the
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
.
Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries. In the
binary numeral system
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" ( one).
The base-2 numeral system is a positional notatio ...
, a special case signed-digit representation is the ''
non-adjacent form'', which can offer speed benefits with minimal space overhead.
History
Challenges in
calculation
A calculation is a deliberate mathematical process that transforms one or more inputs into one or more outputs or ''results''. The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm, to th ...
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
Florian Cajori (February 28, 1859 – August 14 or 15, 1930) was a Swiss-American historian of mathematics.
Biography
Florian Cajori was born in Zillis, Switzerland, as the son of Georg Cajori and Catherine Camenisch. He attended schools first ...
noted the recurring theme of signed digits, starting with
Colson (1726) and
Cauchy
Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
(1840). In his book ''History of Mathematical Notations'', Cajori titled the section "Negative numerals". For completeness, Colson uses examples and describes
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
(pp. 163–4),
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
(pp. 165–6) and
division
Division or divider may refer to:
Mathematics
*Division (mathematics), the inverse of multiplication
*Division algorithm, a method for computing the result of mathematical division
Military
*Division (military), a formation typically consisting ...
(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 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 it. Another German usage of signed-digits was described in 1902 in
Klein's encyclopedia
Felix Klein's ''Encyclopedia of Mathematical Sciences'' is a German mathematical encyclopedia published in six volumes from 1898 to 1933. Klein and Wilhelm Franz Meyer were organizers of the encyclopedia. Its full title in English is ''Encycloped ...
.
Definition and properties
Digit set
Let
be a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
of
numerical digits
A numerical digit (often shortened to just digit) is a single symbol used alone (such as "2") or in combinations (such as "25"), to represent numbers in a positional numeral system. The name "digit" comes from the fact that the ten digits (Latin ...
with
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
(If
, then the positional number system is
trivial
Trivia is information and data that are considered to be of little value. It can be contrasted with general knowledge and common sense.
Latin Etymology
The ancient Romans used the word ''triviae'' to describe where one road split or forked ...
and only represents the
trivial ring
In ring theory, a branch of mathematics, the zero ring or trivial ring is the unique ring (up to isomorphism) consisting of one element. (Less commonly, the term "zero ring" is used to refer to any rng of square zero, i.e., a rng in which for a ...
), with each digit denoted as
for
is known as the
radix
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is t ...
or
number base
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is t ...
.
can be used for a signed-digit representation if it's associated with a unique
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
such that
for all
This function,
is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in
One benefit of this formalism is that the definition of "the integers" (however they may be defined) is not conflated with any particular system for writing/representing them; in this way, these two distinct (albeit closely related) concepts are kept separate.
can be
partitioned into three distinct sets
,
, and
, representing the positive, zero, and negative digits respectively, such that all digits
satisfy
, all digits
satisfy
and all digits
satisfy
. The cardinality of
is
, the cardinality of
is
, and the cardinality of
is
, giving the number of positive and negative digits respectively, such that
.
Balanced form representations
Balanced form representations are representations where for every positive digit
, there exist a corresponding negative digit
such that
. It follows that
. Only
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
bases can have balanced form representations, as otherwise
has to be the opposite of itself and hence 0, but
. In balanced form, the negative digits
are usually denoted as positive digits with a bar over the digit, as
for
. For example, the digit set of
balanced ternary
Balanced ternary is a ternary numeral system (i.e. base 3 with three digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanc ...
would be
with
,
, and
. This convention is adopted in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s of odd
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
order
:
:
Dual signed-digit representation
Every digit set
has a
dual digit set
given by the
inverse order of the digits with an
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
defined by
. As a result, for any signed-digit representations
of a number system
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
constructed from
with
valuation , there exists a dual signed-digit representations of
,
, constructed from
with
valuation , and an isomorphism
defined by
, where
is the additive inverse operator of
. The digit set for balanced form representations is
self-dual
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a Injective function, one-to-one fashion, often (but not always) by means of an Involution (mathematics), involutio ...
.
For integers
Given the digit set
and function
as defined above, let us define an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
endofunction
In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a grou ...
as the following:
:
If the only
periodic point In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function is a point which the system returns to after a certain number of function iterations or a certain amount of time.
Iterated functions
Given a ...
of
is the
fixed point , then the set of all signed-digit representations of the
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
using
is given by the
Kleene plus
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
, the set of all finite
concatenated
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
strings of digits
with at least one digit, with
. Each signed-digit representation
has a
valuation
:
.
Examples include
balanced ternary
Balanced ternary is a ternary numeral system (i.e. base 3 with three digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanc ...
with digits
.
Otherwise, if there exist a non-zero
periodic point In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function is a point which the system returns to after a certain number of function iterations or a certain amount of time.
Iterated functions
Given a ...
of
, then there exist integers that are represented by an infinite number of non-zero digits in
. Examples include the standard
decimal numeral system with the digit set
, which requires an
infinite number of the digit to represent the
additive inverse
In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...
, as
, and the positional numeral system with the digit set
with
, which requires an infinite number of the digit
to represent the number
, as
.
For decimal fractions
If the integers can be represented by the
Kleene plus
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
, then the set of all signed-digit representations of the
decimal fraction
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic num ...
s, or
-adic rationals