一進記数法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

改名提案：この記事のタイトルに関して「1進記数法」もしくは「1進法」への改名が提案されています。詳細はノート:位取り記数法を参照してください。

一進記数法（いっしんきすうほう）は数の表現方法の1つで、一を基数とする非標準的な記数法である。任意の記号をN回繰り返すことで数Nを表すもので、自然数を表現するもっとも単純な記数法である。単に一進法（いっしんほう）ともいう。従来このような記数法には特定の名称が無かったので便宜的に名づけられた。n進記数法(n>1)という位取り記数法と混同しないよう注意が必要である。

例えば記号として | （tally mark）を使うと、6は |||||| として表される。また、指を折って数を数えるやり方は一進記数法であるといえる。一進記数法はスポーツの試合で得点を数えるなど、進行中の結果を集計するのに便利である。これは書き足していくだけのインクリメンタルな記数法である、つまり中間結果を消したり、捨てたりする必要がないからである。

| を使うのは欧米ではもっとも一般的な方法である。単位となるマークは読みやすいように5つごとのグループにまとめられることが多い。これは十進記数法で 100,000,000 のような大きな数を読みやすくするために（スペースやコンマなどの）区切り記号を使うのに似ている。グループの中の1番目または5番目のマークは簡単に識別できるように他のマークに対して斜めに書かれることがある。5を表すマークはfive-bar gateとも呼ばれる。グループを2つまとめて円で囲む（10を表す）こともある。

日本や中国では五画の漢字である正を書いて数を数える方法があるが、これも5つごとのグループでまとめる一進記数法である。

アルゼンチンやブラジルではTruco(en)というゲームを遊ぶときなどに一進記数法が広く用いられる。

加算や減算は一進記数法では特に簡単であり、ほぼ記号列の連結だけで済む。乗算や除算はそれより面倒な手順となる。

他の一般的な基数の記数法とは違い、一進記数法には0を表す記号がない。もし0を表す記号があったなら、二進記数法になってしまう。真の一進記数法には「何もない」を明示的に表す方法はなく、暗黙的には何も書かないことで表される。ローマ数字のような高度な数の数え方でも0にあたる文字はなく、代わりにラテン語で「何もない」を意味するnullaeと書く。

標準的な位取り記数法と比較して、大きな数の計算には一進記数法は不便なので使われない。また固定的な文書で使われることもほとんどない。

一進記数法は理論計算機科学で決定問題（P完全な問題など）の記述において問題に必要な時間・空間計算量を「人工的に」減らすために使われることがある。例として、素因数分解の問題は入力が二進法で与えられると、入力長の多項式時間以上の実行時間を必要とすると考えられている。しかし入力が一進法で与えられるならば、線形の実行時間しか必要としない。もちろんこれはミスリードであり、一進法の入力が与えられても実際の実行時間が短くなることはない。二進法での入力長は入力の数の対数に比例するが、一進法での入力長は入力の数（それ自身）に比例するからである。よって一進法のほうが時間・空間計算量を入力長の関数として表すと優れているように見えるが、入力が表す数の関数としては（実際には）劣っているのである。