actions

三進法

三進法(さんしんほう)とは、3(てい、基(base)とも)とし、底のの和で数を表現する方法である。

概要

任意の正の数は次のように表すことが出来る。

[math]a_N3^N + a_{N-1}3^{N-1} + \cdots + a_1 3 + a_0 + {a_{-1}\over 3} + {a_{-2}\over 3^2} + \cdots [/math]

am は0,1,2のどれか)このとき、

[math]a_Na_{N-1}\ldots a_1a_0.a_{-1}a_{-2}\ldots[/math]

と書くのが三進法である。

演算

三進法で記した、加算及び乗算の表は次のようになる。

加算
  0 1 2
0 0 1 2
1 1 2 10
2 2 10 11
乗算
  0 1 2
0 0 0 0
1 0 1 2
2 0 2 11

三進法には、そのどこかの桁で丸め(端数処理)を行おうとする時に、例えば十進法における 0.5 のような面倒な場合が無い、という特徴がある。さらに後述する平衡三進法には、ある桁で打ち切るだけで「一捨二入」の丸めになる、という特長がある。

経済性

コンピュータなどの計算機械で、N進記法でひとケタを表現・記憶するコストがNに比例すると仮定する。すると、最大値Mまでを表現・記憶できるようにするためのコストは、一桁分のコストに必要な桁数を掛けたものとなり、具体的には N × logNM である。この値が極小になるのはNネイピア数eの時であるが、e進法は通常の数の表現には全く適さない。前後の整数では、2進と4進の場合が同じで、3進の場合が若干だが小さな値となる。よって前述の仮定の下では3進法の採用が最も経済的ということになるが、3値素子といったようなものは、特に電子的には2値素子の扱いやすさとは比べるべくもなく、稀である。が、後述する平衡三進法を使っていたソ連のコンピュータw:Setunなど、全く例がないわけでもない。

以上の計算では、仮定としてN進の場合にはN個の素子が必要としているわけだが、実際には1個の素子で、2状態(オン・オフ)や3状態(実用例のある3値素子としては、2方向の磁化と無磁化など)のものを使うことがもっぱらのため、そもそも仮定が実際とは違っている(10進法の計算機などで、10個の素子を使うものもないわけではない)。

平衡三進法

重みを持つ各桁の値を負の側にも振る、平衡位取り記数法の最も単純な方式である(同様の考え方を拡張すれば、平衡五進法や平衡七進法が考えられる)。amの値を-1,0,1とする。位取り記数法の内に負の数も含めて綺麗に表現できるという性質があり、ドナルド・クヌースのように「おそらく、あらゆる記数法の中で最も美しい」と言う者もいる[1]。しかし、日常使う十進法や他の通常の記数法と色々な点で違うことと、二進法などと比べ応用も多くないため、ほとんど使われない。ここでは-1を[math]\bar{1}[/math]と表示することとする。この表記法は天秤で1g,3g,9g,27gの分銅を用いて1~40gのものの重さを量る方法とよく似ている。

演算

平衡三進法では通常と若干違う演算が必要である。加算、乗算の結果は次のようになる。

加算
  [math]\bar{1}[/math] [math]0[/math] [math]1[/math]
[math]\bar{1}[/math] [math]\bar{1}1[/math] [math]\bar{1}[/math] [math]0[/math]
[math]0[/math] [math]\bar{1}[/math] [math]0[/math] [math]1[/math]
[math]1[/math] [math]0[/math] [math]1[/math] [math]1\bar{1}[/math]
乗算
  [math]\bar{1}[/math] [math]0[/math] [math]1[/math]
[math]\bar{1}[/math] [math]1[/math] [math]0[/math] [math]\bar{1}[/math]
[math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math]
[math]1[/math] [math]\bar{1}[/math] [math]0[/math] [math]1[/math]

上の位に影響を及ぼすのは加算の2つだけである。二進と同様に乗算では上の位に影響を及ぼさない。減算は複雑そうに思えるが、加算の結果を知っていれば難しくない。減算では[math]\bar{1}[/math][math]1[/math]を入れ替えたものを加算する方法も有効である。ただし、除算は厄介である。

それぞれの表記

十進表記 三進表記 平衡三進法
正の数 負の数
0 0 [math]0[/math]
1 1 [math]1[/math] [math]\bar{1}[/math]
2 2 [math]1\bar{1}[/math] [math]\bar{1}1[/math]
3 10 [math]10[/math] [math]\bar{1}0[/math]
4 11 [math]11[/math] [math]\bar{1}\bar{1}[/math]
5 12 [math]1\bar{1}\bar{1}[/math] [math]\bar{1}11[/math]
6 20 [math]1\bar{1}0[/math] [math]\bar{1}10[/math]
7 21 [math]1\bar{1}1[/math] [math]\bar{1}1 \bar{1}[/math]
8 22 [math]10\bar{1}[/math] [math]\bar{1}01[/math]
9 100 [math]100[/math] [math]\bar{1}00[/math]

3値論理との関連

多値論理の一種で、それらのうちもっとも単純なものともいえる3値論理と三進法は、ある意味で関連があるとも言えるが、同一視するのは誤りである。3値論理には3値論理としての各種の論理演算が提案されているが、それらは必ずしも記数法としての三進法(通常の、あるいは平衡三進法)と対応するとは限らないし、対応させなければならない、というものでもない。論理素子・回路として3状態の方式を使い、数の表現と数値計算に三進法を採用したコンピュータがあったとして、そのコンピュータが論理演算として3値論理の論理演算を持つか否か(あるいはそれがどのような論理体系を実装したものか)も設計次第である(前述のソ連のSetunに関して、三進法の回路方式を、すなわち3値論理であると解釈したものと思われる解説などが見られることがある)。

  1. 『The Art of Computer Programming』日本語版(アスキー)2巻 p. 194

関連項目

参考文献