Унарна система числення це en система числення із 1 Це найпростіша система числення для представлення дійсних чисел для

Унарна система числення — це ^[en] система числення із -1. Це найпростіша система числення для представлення дійсних чисел: для того, щоб в ній представити число N, довільно вибраний символ, який використовується як 1 повторюється N разів. Наприклад, числа 1, 2, 3, 4, 5, … будуть виглядати в такій системі як показано нижче

1, 11, 111, 1111, 11111, …

Ці числа не слід плутати із репюнітами, які також задаються у вигляді послідовностей одиниць але мають свою звичайне десяткову числову інтерпретацію.

Застосування

Унарні числа використовуються в деяких алгоритмах стиснення даних, таких як код Голомба. Це поняття також є основою для аксіом Пеано, що формалізують арифметику в рамках математичної логіки. Форма унарної нотації, яка називається ^[en] використовується для представлення чисел в Лямбда-численні.

Складність

У порівнянні зі стандартним позиційним записом, унарна система незручна і тому не використовується на практиці для великих обчислень. Вона зустрічається в описах деяких проблем вибору в теорії алгоритмів (наприклад в деяких ^[en] задачах), де її використовують, щоб «штучно» зменшити час виконання або просторові вимоги задачі. Наприклад, підозрюють, що задача факторизації цілих чисел вимагає часу виконання більшого ніж поліномна функція від довжини її входу в двійковому записі, але їй потрібен лише лінійний час якщо вхід представлено унарно. Однак, це потенційно оманливо. Використання унарного входу повільніше для будь-якого заданого числа, не швидше. Відмінність у тому, що двійковий (або більшої основи) вхід пропорційний логаритму з основою два (або більше) числа тоді як унарний вхід пропорційний самому числу. Отже, хоча з унарною системою час виконання і просторові вимоги як функції від довжини входу виглядають краще, вони не представляють дієвішого розв'язання.

У теорії складності обчислень, унарні числа використовуються, щоб відрізнити ^[en] задачі від NP-повних, але не сильно NP-повних. Задача, що має на вході якісь числові параметри сильно NP-повна, якщо вона залишається NP-повною навіть коли розмір входу штучно збільшують переводячи його в унарну систему. Для такої задачі, існують складні випадки для яких значення всіх параметрів майже поліномно великі.

Примітки

Hodges, Andrew (2009), One to Nine: The Inner Life of Numbers, Anchor Canada, с. 14, ISBN , The simplest way to write the natural numbers is by the unary notation.
Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994), Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing (вид. 2nd), Academic Press, с. 117, ISBN , the base 1 (or unary) representation of the number $x$ is simply a string of ones of length $x$ .
Hext, Jan (1990), Programming Structures: Machines and programs, Programming Structures, т. 1, Prentice Hall, с. 33, ISBN .
(1966), Run-length encodings, IEEE Transactions on Information Theory, IT-12 (3): 399—401, doi:10.1109/TIT.1966.1053907.
Magaud, Nicolas; Bertot, Yves (2002), Changing data structures in type theory: a study of natural numbers, Types for proofs and programs (Durham, 2000), Lecture Notes in Comput. Sci., т. 2277, Springer, Berlin, с. 181—196, doi:10.1007/3-540-45842-5_12, MR 2044538.
Jansen, Jan Martin (2013), Programming in the λ-calculus: from Church to Scott and back, The Beauty of Functional Code: Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday, Lecture Notes in Computer Science, т. 8106, Springer-Verlag, с. 168—180, doi:10.1007/978-3-642-40355-2_12.
; Barak, Boaz (2007), The computational model —and why it doesn't matter [Обчислювальна модель і чому вона не має значення] (PDF), Computational Complexity: A Modern Approach [Обчислювальна складність: Сучасний підхід] (вид. січень 2007, чорнетка), Cambridge University Press, §17, с. 32–33, процитовано 10 травня 2017.
Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation [Природа обчислень], Oxford University Press, с. 29, ISBN .
Garey, M. R.; Johnson, D. S. (1978), 'Strong' NP-completeness results: Motivation, examples, and implications [Висліди в сильній NP-повноті: Спонука, приклади і наслідки], Journal of the ACM, 25 (3): 499—508, doi:10.1145/322077.322090, MR 0478747, S2CID 18371269.

[1] Hodges, Andrew (2009), One to Nine: The Inner Life of Numbers, Anchor Canada, с. 14, ISBN , The simplest way to write the natural numbers is by the unary notation.

[2] Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994), Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing (вид. 2nd), Academic Press, с. 117, ISBN , the base 1 (or unary) representation of the number $x$ is simply a string of ones of length $x$ .

[3] Hext, Jan (1990), Programming Structures: Machines and programs, Programming Structures, т. 1, Prentice Hall, с. 33, ISBN .

[4] (1966), Run-length encodings, IEEE Transactions on Information Theory, IT-12 (3): 399—401, doi:10.1109/TIT.1966.1053907.

[5] Magaud, Nicolas; Bertot, Yves (2002), Changing data structures in type theory: a study of natural numbers, Types for proofs and programs (Durham, 2000), Lecture Notes in Comput. Sci., т. 2277, Springer, Berlin, с. 181—196, doi:10.1007/3-540-45842-5_12, MR 2044538.

[6] Jansen, Jan Martin (2013), Programming in the λ-calculus: from Church to Scott and back, The Beauty of Functional Code: Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday, Lecture Notes in Computer Science, т. 8106, Springer-Verlag, с. 168—180, doi:10.1007/978-3-642-40355-2_12.

[7] ; Barak, Boaz (2007), The computational model —and why it doesn't matter [Обчислювальна модель і чому вона не має значення] (PDF), Computational Complexity: A Modern Approach [Обчислювальна складність: Сучасний підхід] (вид. січень 2007, чорнетка), Cambridge University Press, §17, с. 32–33, процитовано 10 травня 2017.

[8] Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation [Природа обчислень], Oxford University Press, с. 29, ISBN .

[9] Garey, M. R.; Johnson, D. S. (1978), 'Strong' NP-completeness results: Motivation, examples, and implications [Висліди в сильній NP-повноті: Спонука, приклади і наслідки], Journal of the ACM, 25 (3): 499—508, doi:10.1145/322077.322090, MR 0478747, S2CID 18371269.