The unary numeral system is the simplest numeral system to represent
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s: to represent a number ''N'', a symbol representing 1 is repeated ''N'' times.
In the unary system, the number
0 (zero) is represented by the
empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
, that is, the absence of a symbol. Numbers 1, 2, 3, 4, 5, 6, ... are represented in unary as 1, 11, 111, 1111, 11111, 111111, ...
Unary is a
bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
numeral system. However, because the value of a digit does not depend on its position, it is not a form of
positional notation, and it is unclear whether it would be appropriate to say that it has a
base (or "radix") of
1, as it behaves differently from all other bases.
The use of
tally marks
Tally marks, also called hash marks, are a unary numeral system ( arguably).
They are a form of numeral used for counting. They are most useful in counting or tallying ongoing results, such as the score in a game or sport, as no intermediate ...
in counting is an application of the unary numeral system. For example, using the tally mark | (𝍷), the number 3 is represented as |||. In
East Asia
East Asia is the eastern region of Asia, which is defined in both Geography, geographical and culture, ethno-cultural terms. The modern State (polity), states of East Asia include China, Japan, Mongolia, North Korea, South Korea, and Taiwan. ...
n cultures, the number 3 is represented as
三, a character drawn with three strokes. (One and two are represented similarly.) In China and Japan, the character ćŁ, drawn with 5 strokes, is sometimes used to represent 5 as a tally.
Unary numbers should be distinguished from
repunit
In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book ''Recreat ...
s, which are also written as sequences of ones but have their usual
decimal
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 numeral ...
numerical interpretation.
Operations
Addition and
subtraction are particularly simple in the unary system, as they involve little more than
string concatenation
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 concatenati ...
. The
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string ...
or population count operation that counts the number of nonzero bits in a sequence of binary values may also be interpreted as a conversion from unary to
binary number
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 ...
s.
[.] However,
multiplication is more cumbersome and has often been used as a test case for the design of
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s.
Complexity
Compared to standard
positional numeral systems, the unary system is inconvenient and hence is not used in practice for large calculations. It occurs in some
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
descriptions in
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
(e.g. some
P-complete In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.
The notion of P-complete decision problems is usef ...
problems), where it is used to "artificially" decrease the run-time or space requirements of a problem. For instance, the problem of
integer factorization is suspected to require more than a polynomial function of the length of the input as run-time if the input is given in
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
, but it only needs linear runtime if the input is presented in unary. However, this is potentially misleading. Using a unary input is slower for any given number, not faster; the distinction is that a binary (or larger base) input is proportional to the base 2 (or larger base) logarithm of the number while unary input is proportional to the number itself. Therefore, while the run-time and space requirement in unary looks better as function of the input size, it does not represent a more efficient solution.
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, unary numbering is used to distinguish
strongly NP-complete problems from problems that are
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
but not strongly NP-complete. A problem in which the input includes some numerical parameters is strongly NP-complete if it remains NP-complete even when the size of the input is made artificially larger by representing the parameters in unary. For such a problem, there exist hard instances for which all parameter values are at most polynomially large.
Applications
Unary numbering is used as part of some data compression algorithms such as
Golomb coding
Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb ...
. It also forms the basis for the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
for formalizing arithmetic within
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
.
A form of unary notation called
Church encoding
In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded da ...
is used to represent numbers within
lambda calculus.
[.]
See also
*
Unary coding
Unary coding, or the unary numeral system and also sometimes called thermometer code, is an entropy encoding that represents a natural number, ''n'', with a code of length ''n'' + 1 ( or ''n'' ), usually ''n'' ones followed by a zero (if ...
*
One-hot encoding
In digital circuits and machine learning, a one-hot is a group of Bit, bits among which the legal combinations of values are only those with a single high (1) bit and all the others low (0). A similar implementation in which all bits are '1' exc ...
References
External links
* {{OEIS el, sequencenumber=A000042, name=Unary representation of natural numbers
Numeral systems
1 (number)
Elementary mathematics
Coding theory
Formal languages