一進法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

一進法(いっしんほう)とはの表現方法の1つで、1を底とする非標準的な記数法である。その名に反し、N 進法N を 1 にしたものとは異なるが、後述のように両者に関係はある。

概要[編集]

一進法とは、任意の記号N 回繰り返すことで数 N を表すもので、自然数を表現するもっとも単純な記数法である。例えば記号として 1 を利用した場合、十進法の 1, 2, 3, 4, 5 は一進法で以下のようになる:

1, 11, 111, 1111, 11111.

一進法には 0 を表す記号がなく、0 は空文字列(すなわち、なにも書かない)によって表す。しかしなにも書かないと読者にわからなくなってしまうので、便宜上εで空文字列を表す事もある。

N 進数との関係[編集]

N 進数表記

は自然数

を表している。ここで、形式的に

とすると、表記

 (1 を N 個並べたもの)

を表す事になり、一進数表記と一致する。これが「一進数」と呼ばれる由縁である。

日常生活における具体的[編集]

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

タリーマーク

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

正の字

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

アルゼンチンなどで使われ画線法

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

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

計算機科学における一進法[編集]

一進法は計算機科学計算量を「人工的に」減らすために使われることがある。例として、自然数の素因数分解問題は入力が二進法で与えられる場合には、入力長 n多項式時間では実行不可能だと考えられている(素因数分解仮定)。しかし入力が一進法で与えられるならば、入力長の多項式時間で実行するのは容易である(エラトステネスの篩で十分)。二進法での入力長 n は入力の数 N対数 log N に比例するが、一進法での入力長は入力の数 N それ自身に比例するからである。

関連項目[編集]

以下、英語版の記事

外部リンク[編集]