일진법

3. 연산

일진법에서 덧셈과 뺄셈은 문자열 연결과 거의 같아 매우 간단하다.^[9] 비트열에서 0이 아닌 비트 수를 세는 해밍 가중치(Hamming weight) 또는 개체 수 계산 연산은 일진법에서 이진법으로의 변환으로 해석할 수 있다.^[10]

3. 1. 덧셈

3. 2. 뺄셈

3. 3. 곱셈

4. 계산 복잡도

위치 기수법과 비교하여 일진법은 큰 수를 표현하기 불편하여 대규모 계산에는 실제로 사용되지 않는다. 하지만 계산 이론에서 일부 결정 문제(예: 일부 P-완전 문제) 설명에 나타나는데, 여기서는 문제의 실행 시간 또는 공간 요구 사항을 "인위적으로" 줄이는 데 사용된다.^[14]

N진법 표기에서

:$a\_\{n-1\}\backslash ldots\; a\_0$는 자연수

:$\backslash sum\_\{i=0\}^\{n-1\}a\_iN^i$를 나타낸다.

형식적으로

:$N=1,\backslash ;\; a\_\{n-1\}=\backslash cdots=a\_0=1$이라 하면, 표기 :$1\backslash cdots\; 1$(1을 N개 나열한 것)는

:$\backslash sum\_\{i=0\}^\{n-1\}1\backslash cdot\; 1^i=n$을 나타내게 되고, 일진법 표기와 일치한다. 이것이 「일진법」이라고 불리는 연유이다.

4. 1. 정수 인수분해 문제

4. 2. 강하게 NP-완전 문제

5. 응용

일진법은 계산 이론에서 계산량을 "인위적으로" 줄이기 위해 응용되기도 한다. 예를 들어, 자연수의 소인수분해 문제는 입력이 이진법으로 주어지는 경우, 입력 길이 ''n''의 다항식 시간으로는 풀기 어렵다고 알려져 있다(소인수분해 가정). 그러나 입력이 일진법으로 주어지면, 입력 길이의 다항식 시간으로 푸는 것이 가능하다(에라토스테네스의 체로 충분하다). 이진법에서 입력 길이 ''n''은 입력 수 ''N''의 로그 log ''N''에 비례하지만, 일진법에서 입력 길이는 입력 수 ''N'' 자체에 비례하기 때문이다.

그 외에도 컴퓨터 과학 등에 여러 응용 사례가 있다. 예를 들어, 튜링 기계의 초보적인 예제에서는 테이프 위에 숫자를 나열하여 위치 기수법으로 다루는 것은 상당히 번잡하지만, 일진법을 사용하면 "오른쪽으로 가서 1이 있으면 0으로 바꾸고, 왼쪽으로 간다"와 같은 간단한 절차로 처리할 수 있다.

5. 1. 데이터 압축

5. 2. 수리 논리학

5. 3. 람다 대수

5. 4. 스팸 필터

참조

_[1] 서적 One to Nine: The Inner Life of Numbers https://books.google[...] Anchor Canada
_[2] 서적 Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science https://books.google[...] Academic Press
_[3] 서적 Programming Structures: Machines and Programs Prentice Hall
_[4] 간행물 Third Base http://www.americans[...] 2013-07-28
_[5] 간행물 On efficiency of notations for natural numbers
_[6] 간행물 The Evolution of Modern Numerals from Ancient Tally Marks https://books.google[...]
_[7] 간행물 Chinese Tally Mark
_[8] 문서 Unicode Consortium https://www.unicode.[...] 2016-01-27
_[9] 서적 Logic and computational complexity (Indianapolis, IN, 1994) https://archive.org/[...] Springer, Berlin
_[10] 서적 Computer Science and Statistics--Tenth Annual Symposium on the Interface https://books.google[...] U.S. Department of Commerce / National Bureau of Standards
_[11] 서적 Introduction to Automata Theory, Languages, and Computation https://archive.org/[...] Addison Wesley
_[12] 서적 The New Turing Omnibus: Sixty-Six Excursions in Computer Science https://books.google[...] Computer Science Press
_[13] 서적 Turing Machine Universality of the Game of Life https://books.google[...] Springer
_[14] 서적 Computational Complexity: A Modern Approach Cambridge University Press 2017-05-10
_[15] 서적 The Nature of Computation https://books.google[...] Oxford University Press
_[16] 간행물 'Strong' NP-completeness results: Motivation, examples, and implications
_[17] 간행물 Run-length encodings http://urchin.earth.[...]
_[18] 서적 Types for proofs and programs (Durham, 2000) Springer, Berlin
_[19] 서적 The Beauty of Functional Code Springer-Verlag
_[20] 웹사이트 Email, Spam Control, How to get service for departmental email servers http://answers.uilli[...]
_[21] 간행물 システムの進化と創造性 青土社 1994-05-01