View source for Unary numeral system

{{short description|Base-1 numeral system}}
{{Numeral systems}}
{{CS1 config|mode=cs2}}
The '''unary numeral system''' is the simplest numeral system to represent [[natural number]]s:<ref>{{citation|title=One to Nine: The Inner Life of Numbers|first=Andrew|last=Hodges|publisher=Anchor Canada|year=2009|isbn=9780385672665|page=14|url=https://books.google.com/books?id=UCuwrtBax7AC&pg=PA14}}.</ref> to represent a number ''N'', a symbol representing 1 is repeated ''N'' times.<ref>{{citation|title=Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science|first1=Martin|last1=Davis|first2=Ron|last2=Sigal|first3=Elaine J.|last3=Weyuker|edition=2nd|publisher=Academic Press|year=1994|series=Computer Science and Scientific Computing|isbn=9780122063824|page=117|url=https://books.google.com/books?id=GRWOqKwZGRAC&pg=PA117}}.</ref>

In the unary system, the number [[0]] (zero) is represented by the [[empty string]], 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, ...<ref>{{citation|page=33|title=Programming Structures: Machines and Programs|volume=1|first=Jan|last=Hext|publisher=Prentice Hall|year=1990|isbn=9780724809400}}.</ref>

Unary is a [[Bijective numeration|bijective numeral system]]. However, although it has sometimes been described as "base 1",<ref>{{citation | title = Third Base | author = Brian Hayes | author-link = Brian Hayes (scientist) | journal = [[American Scientist]] | volume = 89 | issue = 6 | year = 2001 | pages = 490 | doi = 10.1511/2001.40.3268 | url=http://www.americanscientist.org/issues/pub/2001/11/third-base | accessdate=2013-07-28 | archive-url = https://web.archive.org/web/20140111055213/http://www.americanscientist.org/issues/pub/2001/11/third-base | archive-date = 2014-01-11 | url-status = dead | url-access = subscription }}</ref> it differs in some important ways from [[positional notation]]s, in which the value of a digit depends on its position within a number. For instance, the unary form of a number can be exponentially longer than its representation in other bases.<ref>{{citation
 | last = Zdanowski | first = Konrad
 | doi = 10.1016/j.tcs.2022.02.015
 | journal = Theoretical Computer Science
 | mr = 4410388
 | pages = 1–10
 | title = On efficiency of notations for natural numbers
 | volume = 915
 | year = 2022}}</ref>

The use of [[tally marks]] in counting is an application of the unary numeral system. For example, using the tally mark '''{{pipe}}''' (𝍷), the number 3 is represented as '''{{pipe}}{{pipe}}{{pipe}}'''. In [[East Asia]]n cultures, the number 3 is represented as [[wikt:三#Translingual|三]], a character drawn with three strokes.<ref>{{citation|journal=[[American Mathematical Monthly]]|volume=16|issue=8–9|pages=125–33|first=Charles E.|last=Woodruff|title=The Evolution of Modern Numerals from Ancient Tally Marks|url=https://books.google.com/books?id=JggPAAAAIAAJ&pg=PA125|doi=10.2307/2970818|year=1909|jstor=2970818|url-access=subscription}}.</ref> (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.<ref>{{citation|last=Hsieh |first=Hui-Kuang |year=1981 |title=Chinese Tally Mark |journal=[[The American Statistician]] |volume=35 |issue=3 |page=174 |doi=10.2307/2683999|jstor=2683999 }}</ref><ref name="Lunde 2016-2">{{citation|first1=Ken |last1=Lunde |first2=Daisuke |last2=Miura |url=https://www.unicode.org/L2/L2016/16046-ideo-tally-marks.pdf |id=Proposal L2/16-046 |contribution=Proposal to Encode Five Ideographic Tally Marks |title=Unicode Consortium |date=January 27, 2016}}</ref>

Unary numbers should be distinguished from [[repunit]]s, which are also written as sequences of ones but have their usual [[decimal]] numerical interpretation.

==Operations==
[[Addition]] and [[subtraction]] are particularly simple in the unary system, as they involve little more than [[string concatenation]].<ref>{{citation
 | last = Sazonov
 | first = Vladimir Yu.
 | contribution = On feasible numbers
 | doi = 10.1007/3-540-60178-3_78
 | mr = 1449655
 | pages = [https://archive.org/details/logiccomputation0000unse/page/30 30–51]
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Logic and computational complexity (Indianapolis, IN, 1994)
 | volume = 960
 | year = 1995
 | isbn = 978-3-540-60178-4
 | url = https://archive.org/details/logiccomputation0000unse/page/30
 }}. See in particular p. 48.</ref> The [[Hamming weight]] 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]]s.<ref name="blaxell">{{citation
 | last = Blaxell | first = David
 | editor1-last = Hogben | editor1-first = David
 | editor2-last = Fife | editor2-first = Dennis W.
 | contribution = Record linkage by bit pattern matching
 | pages = 146–156
 | publisher = U.S. Department of Commerce / National Bureau of Standards
 | series = NBS Special Publication
 | title = Computer Science and Statistics--Tenth Annual Symposium on the Interface
 | url = https://books.google.com/books?id=-MrJPUqTPh8C&pg=PA146
 | volume = 503
 | year = 1978}}.</ref> However, [[multiplication]] is more cumbersome and has often been used as a test case for the design of [[Turing machine]]s.<ref>{{citation|at=[https://archive.org/details/introductiontoau00hopc/page/ Example 7.7, pp. 158–159]|title=Introduction to Automata Theory, Languages, and Computation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Jeffrey D.|last2=Ullman|author2-link=Jeffrey Ullman|publisher=Addison Wesley|year=1979|isbn=978-0-201-02988-8|url-access=registration|url=https://archive.org/details/introductiontoau00hopc/page/}}.</ref><ref>{{citation|title=The New Turing Omnibus: Sixty-Six Excursions in Computer Science|first=A. K.|last=Dewdney|author-link=A. K. Dewdney|publisher=Computer Science Press|year=1989|page=209|url=https://books.google.com/books?id=NDiU62j7jeMC&pg=PA209|isbn=9780805071665}}.</ref><ref>{{citation|title=Turing Machine Universality of the Game of Life|volume=18|series=Emergence, Complexity and Computation|first=Paul|last=Rendell|publisher=Springer|year=2015|isbn=9783319198422|url=https://books.google.com/books?id=px8_CgAAQBAJ&pg=PA83|pages=83–86|contribution=5.3 Larger Example TM: Unary Multiplication}}.</ref>

==Complexity==
Compared to standard [[Positional notation|positional numeral systems]], the unary system is inconvenient and hence is not used in practice for large calculations. It occurs in some [[decision problem]] descriptions in [[theory of computation|theoretical computer science]] (e.g. some [[P-complete]] 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 numeral system|binary]], but it only needs linear runtime if the input is presented in unary.<ref>{{citation
 | last1 = Arora | first1 = Sanjeev | author-link1 = Sanjeev Arora (computer scientist)
 | last2 = Barak | first2 = Boaz
 | year = 2007
 | chapter = The computational model&nbsp;—and why it doesn't matter
 | title = Computational Complexity: A Modern Approach
 | publisher = Cambridge University Press
 | at = §17, pp. 32–33
 | edition = January 2007 draft
 | chapter-url = http://www.cs.princeton.edu/theory/complexity/modelchap.pdf
 | access-date = May 10, 2017
 }}.</ref> 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.<ref>{{citation|title=The Nature of Computation|first1=Cristopher|last1=Moore|author1-link=Cristopher Moore|first2=Stephan|last2=Mertens|publisher=Oxford University Press|year=2011|isbn=9780199233212|page=29|url=https://books.google.com/books?id=z4zMiZyAE1kC&pg=PA29}}.</ref>

In [[computational complexity theory]], unary numbering is used to distinguish [[strongly NP-complete]] problems from problems that are [[NP-complete]] 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.<ref>{{citation
 | last1 = Garey | first1 = M. R. | author1-link = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
 | doi = 10.1145/322077.322090
 | issue = 3
 | journal = [[Journal of the ACM]]
 | mr = 478747
 | pages = 499–508
 | title = 'Strong' NP-completeness results: Motivation, examples, and implications
 | volume = 25
 | year = 1978| s2cid = 18371269 | doi-access = free
 }}.</ref>

==Applications==
In addition to the application in tally marks, unary numbering is used as part of some data compression algorithms such as [[Golomb coding]].<ref>{{citation
 | last = Golomb | first = S.W. | author-link = Solomon W. Golomb
 | issue = 3
 | journal = IEEE Transactions on Information Theory
 | pages = 399–401
 | title = Run-length encodings
 | url = http://urchin.earth.li/~twic/Golombs_Original_Paper/
 | volume = IT-12
|doi =10.1109/TIT.1966.1053907
 | year = 1966| url-access = subscription
 }}.</ref> It also forms the basis for the [[Peano axioms]] for formalizing arithmetic within [[mathematical logic]].<ref>{{citation
 | last1 = Magaud | first1 = Nicolas
 | last2 = Bertot | first2 = Yves
 | contribution = Changing data structures in type theory: a study of natural numbers
 | doi = 10.1007/3-540-45842-5_12
 | mr = 2044538
 | pages = 181–196
 | publisher = Springer, Berlin
 | series = Lecture Notes in Comput. Sci.
 | title = Types for proofs and programs (Durham, 2000)
 | volume = 2277
 | year = 2002| isbn = 978-3-540-43287-6
 }}.</ref>
A form of unary notation called [[Church encoding]] is used to represent numbers within [[lambda calculus]].<ref>{{citation
 | last = Jansen | first = Jan Martin
 | title = The Beauty of Functional Code
 | contribution = Programming in the λ-calculus: from Church to Scott and back
 | doi = 10.1007/978-3-642-40355-2_12
 | pages = 168–180
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 8106
 | year = 2013| isbn = 978-3-642-40354-5
 }}.</ref>

Some [[email]] [[spam filter]]s tag messages with a number of [[asterisk]]s in an [[e-mail header]] such as ''X-Spam-Bar'' or ''X-SPAM-LEVEL''. The larger the number, the more likely the email is considered spam. Using a unary representation instead of a decimal number lets the user search for messages with a given rating or higher. For example, searching for '''****''' yield messages with a rating of at least 4.<ref>{{citation | url=http://answers.uillinois.edu/illinois/page.php?id=49002 | title=Email, Spam Control, How to get service for departmental email servers }}</ref>

== See also ==
*[[Unary coding]]
*[[One-hot encoding]]

== References ==
{{reflist|30em}}

== External links ==
{{commons|Unary numeral|Unary numeral system}}
* {{OEIS el|sequencenumber=A000042|name=Unary representation of natural numbers}}

[[Category:Numeral systems]]
[[Category:1 (number)]]
[[Category:Elementary mathematics]]
[[Category:Coding theory]]
[[Category:Formal languages]]