一進法

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

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

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

タリーマーク

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

正の字

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

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

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

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

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

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

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

関連項目[編集]

以下、英語版の記事

外部リンク[編集]