三進法

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

概要[編集]

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

a_{N}3^{N}+a_{N-1}3^{N-1}+\cdots +a_{1}3+a_{0}+{a_{-1} \over 3}+{a_{-2} \over 3^{2}}+\cdots

（ a_m は0,1,2のどれか）このとき、

a_{N}a_{N-1}\ldots a_{1}a_{0}.a_{-1}a_{-2}\ldots

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

記数法[編集]

位取り[編集]

三進法では0、1、2の計三つの数字を用い、三を10、四を11…と表記する。三で桁上がりするので、「3」の字が使えるN進法は四進法以降、「3」の字が使えて「1/3」が割り切れるN進法は六進法以降となる。桁の増加も、三進法では、三の冪数で桁が一つ増える。以下の表に、二進法（底が2）、三進法（底が3）、六進法（底が2×3）、十進法（底が2×5）での各表記法の差異を掲載する。

数列の進み方（十八まで）
二進法	三進法	六進法	十進法
0	0	0	0
1	1	1	1
10	2	2	2
11	10	3	3
100	11	4	4
101	12	5	5
110	20	10	6
111	21	11	7
1000	22	12	8
1001	100	13	9
1010	101	14	10
1011	102	15	11
1100	110	20	12
1101	111	21	13
1110	112	22	14
1111	120	23	15
10000	121	24	16
10001	122	25	17
10010	200	30	18

数列の進み方（十九以降）
二進法	三進法	六進法	十進法
10011	201	31	19
10100	202	32	20
10101	210	33	21
10110	211	34	22
10111	212	35	23
11000	220	40	24
11001	221	41	25
11010	222	42	26
11011	1000	43	27
100100	1100	100	36
110001	1211	121	49
110110	2000	130	54
1000000	2101	144	64
1010001	10000	213	81
1100100	10201	244	100

三進法の位取り
桁	三進法の位数	二進数に換算	三進数	六進数に換算	十進数に換算
整数第七位	729の位	1011011001	1000000	3213	729
整数第六位	243の位	11110011	100000	1043	243
整数第五位	81の位	1010001	10000	213	81
整数第四位	27の位	11011	1000	43	27
整数第三位	9の位	1001	100	13	9
整数第二位	3の位	11	10	3	3
整数第一位	1の位	1	1	1	1
小数第一位	1/3の位	1/11	0.1	0.2	1/3
小数第二位	1/9の位	1/1001	0.01	0.04	1/9
小数第三位	1/27の位	1/11011	0.001	0.012	1/27
小数第四位	1/81の位	1/1010001	0.0001	0.0024	1/81

※ 位数は十進表記。

演算[編集]

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

加算
+	0	1	2
0	0	1	2
1	1	2	10
2	2	10	11

乗算
×	1	2
0	0	0
1	1	2
2	2	11

三は二で割り切れない（= 奇数である）ため、三進法では 1/2 = 0.1111… となり、「1÷偶数」が全て割り切れない。三進法や五進法などの奇数進法は、1/2 が割り切れないため、そのどこかの桁で丸め（端数処理）を行おうとする時に、例えば六進法の 0.3 や十進法の 0.5 のような「二分すると同数」が起こらない、という特徴を持つ。さらに後述する平衡三進法には、ある桁で打ち切るだけで「一捨二入」の丸めになる、という特長を持つ。

しかし、二の次の数である三が底になっているので、「三分すると同数」が起こる、という特徴を持つ。これは、六進法の 0.2 や九進法の 0.3 などと同様である。

三進法の小数と除算
単位分数	除数の素因数分解	三進小数	六進小数	十進小数
1/2	2	0.1111…	0.3	0.5
1/3	3	0.1	0.2	0.3333…
1/4	2²	0.0202…	0.13	0.25
1/5	5	0.0121…	0.1111…	0.2
1/6	2×3	0.0111…	0.1	0.1666…
1/7	7	0.010212…	0.0505…	0.142857…
1/8	2³	0.0101…	0.043	0.125
1/9	3²	0.01	0.04	0.1111…
1/10	2×5	0.0022…	0.03333…	0.1
1/11	11	0.00211…	0.0313452421…	0.0909…
1/12	2²×3	0.00202…	0.03	0.08333…
1/16	2⁴	0.0012…	0.0213	0.0625
1/18	2×3²	0.00111…	0.02	0.05555…
1/20	2²×5	0.0011…	0.01444…	0.05
1/25	5²	0.00100201102212202112…	0.01235…	0.04
1/27	3³	0.001	0.012	0.037…
1/36	2²×3²	0.000202…	0.01	0.02777…
1/64	2⁶	0.0001021011122022…	0.003213	0.015625
1/81	3⁴	0.0001	0.0024	0.012345679…

※ 単位分数と除数の素因数分解は十進表記。

経済性[編集]

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

以上の計算では、仮定としてN進の場合にはN個の素子が必要としているわけだが、実際には一つの素子で、二つの状態（オン・オフ）や三つの状態（実用例のある三値素子としては、二方向の磁化と無磁化など）のものを使うことが専らのため、そもそも仮定が実際とは異なる（十進法の計算機などで、十個の素子を使うものもないわけではないが、それではたいへんに効率が悪く、たいていは2状態の素子4個〜6個をうまく利用して十種類の値を表現している）。

平衡三進法[編集]

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

平衡三進法の演算[編集]

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

加算
+	${\bar {1}}$	$0$	$1$
${\bar {1}}$	${\bar {1}}1$	${\bar {1}}$	$0$
$0$	${\bar {1}}$	$0$	$1$
$1$	$0$	$1$	$1{\bar {1}}$

乗算
×	${\bar {1}}$	$0$	$1$
${\bar {1}}$	$1$	$0$	${\bar {1}}$
$0$	$0$	$0$	$0$
$1$	${\bar {1}}$	$0$	$1$

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

通常のN進法との差異[編集]

十進法	六進法	通常の三進法	平衡三進法
十進法	六進法	通常の三進法	正の数	負の数
0	0	0	$0$
1	1	1	$1$	${\bar {1}}$
2	2	2	$1{\bar {1}}$	${\bar {1}}1$
3	3	10	$10$	${\bar {1}}0$
4	4	11	$11$	${\bar {1}}{\bar {1}}$
5	5	12	$1{\bar {1}}{\bar {1}}$	${\bar {1}}11$
6	10	20	$1{\bar {1}}0$	${\bar {1}}10$
7	11	21	$1{\bar {1}}1$	${\bar {1}}1{\bar {1}}$
8	12	22	$10{\bar {1}}$	${\bar {1}}01$
9	13	100	$100$	${\bar {1}}00$

コンピュータ[編集]

平衡三進法を採用したコンピュータにSetunがある。

3値論理との関連[編集]

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

注[編集]

^ 『The Art of Computer Programming』日本語版（アスキー）2巻 p. 194
^ Donald E. Knuth (1998). The Art of Computer Programming. 2 (3 ed.). Addison Wesley Longman. p. 207. ISBN 0-201-89684-2. "Perhaps the prettiest number system of all is the balanced ternary notation"

参考文献[編集]

ヘンリー・S・ウォーレン・ジュニア『ハッカーのたのしみ（英語版）』 ISBN 4434046683

[1] 『The Art of Computer Programming』日本語版（アスキー）2巻 p. 194

[2] Donald E. Knuth (1998). The Art of Computer Programming. 2 (3 ed.). Addison Wesley Longman. p. 207. ISBN 0-201-89684-2. "Perhaps the prettiest number system of all is the balanced ternary notation"

[1]

[2]