Unary numeral system

Source: Wikipedia, the free encyclopedia.
Part of a series on
Numeral systems
Place-value notation
Hindu–Arabic numerals
East Asian systems
Contemporary
Historic
Other systems
Ancient
Post-classical
Contemporary
By radix/base
Common radices/bases
Non-standard radices/bases
Sign-value notation
Non-alphabetic
Alphabetic
List of numeral systems

The unary numeral system is the simplest numeral system to represent natural numbers:[1] to represent a number N, a symbol representing 1 is repeated N times.[2]

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, ...[3]

Unary is a

1, as it behaves differently from all other bases. [citation needed
]

The use of tally marks in counting is an application of the unary numeral system. For example, using the tally mark | (𝍷), the number 3 is represented as |||. In East Asian cultures, the number 3 is represented as 三, a character drawn with three strokes.[4] (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.[5][6]

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

Operations

string concatenation.[7] 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 numbers.[8] However, multiplication is more cumbersome and has often been used as a test case for the design of Turing machines.[9][10][11]

Complexity

Compared to standard

binary, but it only needs linear runtime if the input is presented in unary.[12][13] 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.[14]

In

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.[15]

Applications

In addition to the application in tally marks, unary numbering is used as part of some data compression algorithms such as Golomb coding.[16] It also forms the basis for the Peano axioms for formalizing arithmetic within mathematical logic.[17] A form of unary notation called Church encoding is used to represent numbers within lambda calculus.[18]

Some

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.[19]

See also

References

  1. ISBN 9780385672665
    .
  2. ISBN 9780122063824
    .
  3. ISBN 9780724809400
    .
  4. JSTOR 2970818
    .
  5. JSTOR 2683999
  6. ^ Lunde, Ken; Miura, Daisuke (January 27, 2016), "Proposal to Encode Five Ideographic Tally Marks", Unicode Consortium (PDF), Proposal L2/16-046
  7. MR 1449655
    . See in particular p.  48.
  8. ^ Blaxell, David (1978), "Record linkage by bit pattern matching", in Hogben, David; Fife, Dennis W. (eds.), Computer Science and Statistics--Tenth Annual Symposium on the Interface, NBS Special Publication, vol. 503, U.S. Department of Commerce / National Bureau of Standards, pp. 146–156.
  9. ISBN 978-0-201-02988-8
    .
  10. ISBN 9780805071665
    .
  11. ISBN 9783319198422
    .
  12. ^ Arora, Sanjeev; Barak, Boaz (2007), "The computational model —and why it doesn't matter" (PDF), Computational Complexity: A Modern Approach (January 2007 draft ed.), Cambridge University Press, §17, pp. 32–33, retrieved May 10, 2017.
  13. ^ Feigenbaum, Joan (Fall 2012), CPSC 468/568 HW1 Solution Set (PDF), Computer Science Department, Yale University, retrieved 2014-10-21. [permanent dead link]
  14. ISBN 9780199233212
    .
  15. S2CID 18371269
    .
  16. doi:10.1109/TIT.1966.1053907
    .
  17. MR 2044538
    .
  18. ISBN 978-3-642-40354-5
    .
  19. ^ http://answers.uillinois.edu/illinois/page.php?id=49002

External links

Wikimedia Commons has media related to Unary numeral system.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Unary_numeral_system&oldid=1190679100"